Skip to main content
Aaron Roth's user avatar
Aaron Roth's user avatar
Aaron Roth's user avatar
Aaron Roth
  • Member for 13 years, 8 months
  • Last seen more than 2 years ago
39 votes
3 answers
5k views

Max-cut with negative weight edges

34 votes
5 answers
3k views

Evidence that PPAD is hard?

20 votes
3 answers
428 views

Property testing in other metrics?

16 votes
1 answer
1k views

Separation between coarse correlated equilibria and correlated equilibria

13 votes
4 answers
824 views

A Multi-cut Problem

13 votes
2 answers
657 views

Estimating VC-Dimension

12 votes
2 answers
402 views

Computational query complexity of SQ-learning

11 votes
4 answers
491 views

Dimensionality reduction with slack?

11 votes
1 answer
443 views

Agnostic learning over arbitrary distributions

11 votes
1 answer
1k views

$\epsilon$-nets with respect to the cut norm

10 votes
2 answers
2k views

Maximizing sum edge weights

10 votes
4 answers
522 views

Interesting functions on graphs that can be efficiently maximized.

9 votes
2 answers
226 views

Bounding the rate of increase of the price of anarchy across equilibrium concepts

8 votes
2 answers
550 views

VC Dimension generalized to discrete, non-binary, unordered domains?

7 votes
2 answers
269 views

Counting Metrics

7 votes
1 answer
493 views

Is the convex combination of two potential games a potential game?