# Tag Info

Accepted

### The SQ argument in Balazs Szorenyi's paper

This is a standard adversary argument, not very different from adversary arguments taught in undergraduate algorithms courses. If you are unfamiliar with such arguments, then you can check out these ...

### Constant Width Max Sum Product Multi-objective Shortest path problem

For K=2, PARTITION reduces to this problem, so it is NP-hard. Take an instance of PARTITION: a list of nonnegative integers $x_1,\dots ,x_n$, and you ask if there is a subset $I\subseteq [1,n]$ such ...
• 7,653
Accepted

### Max Sum Product Multi-objective Shortest path problem

It seems NP-complete even with weights in $\{0,1\}$. I reduce from the MINSAT problem: given a SAT instance, find an assignment that minimizes the number of satisfied clauses. More precisely, an ...
• 7,653
Accepted

### Stochastic gradient methods and risk of neural nets

The question has changed somewhat in the comments, so I'll address its new version: "Given a class of algorithms $A$ and an $\epsilon >0$ and a loss class $L$ and a data distribution $D$, one ...
• 10k
1 vote

### About assumptions needed to get convergence of stochastic gradient methods on non-convex objectives

There is a lot of recent work on these questions spurred by interest in deep learning and other non-convex optimization tasks. If the objective is differentiable and smooth (i.e. if the gradient is ...
• 41
1 vote

### What is the probability of a virus spreading through a network given a virus source node?

Given that you are assuming an infinite graph, I am not sure if it is possible at all to find the probability of having all the nodes infected. I would say for any $t > 0$, the probability is (...
• 31
1 vote

### What is the probability of a virus spreading through a network given a virus source node?

there are many "spread" models, what you request does seem to have been studied. eg this paper builds a framework to analyze the difference & distinguish between random virus spreading and network-...
• 10.8k

Only top scored, non community-wiki answers of a minimum length are eligible