4 votes
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 ...
user avatar
4 votes

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 ...
user avatar
  • 7,653
2 votes
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 ...
user avatar
  • 7,653
2 votes
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 ...
user avatar
  • 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 ...
user avatar
  • 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 (...
user avatar
  • 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-...
user avatar
  • 10.8k

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