User Luca Trevisan

34 votes

Accepted

Hierarchy theorem for circuit size

answered Feb 24, 2011 at 7:59

33 votes

Accepted

Fourier coefficients Boolean Functions described by Bounded Depth Circuits with AND OR and XOR gates

answered Nov 28, 2010 at 22:25

24 votes

Accepted

Proving lower bounds by proving upper bounds

answered Nov 28, 2010 at 20:43

22 votes

The importance of Integrality Gap

answered Dec 22, 2010 at 3:13

20 votes

Accepted

Subexponentially solvable hard graph problems

answered Dec 8, 2010 at 16:24

17 votes

Accepted

Non-Uniform vs. Uniform Adversaries

answered Apr 20, 2011 at 22:12

16 votes

Accepted

Simple Constructions of Special Graph Families

answered Mar 13, 2011 at 19:01

16 votes

Accepted

Do runtimes for P require EXP resources to upper-bound? … are concrete examples known? (answer: yes and yes)

answered Feb 3, 2011 at 7:59

14 votes

Computing any information about Max-3SAT

answered Feb 3, 2011 at 5:27

14 votes

Accepted

Is MAX CUT approximation resistant?

answered Dec 19, 2010 at 3:47

12 votes

Bounded-cardinality bounded-frequency set cover: hardness of approximation

answered Dec 22, 2010 at 2:43

11 votes

Accepted

Existence of long induced paths in expander graphs

answered Aug 11, 2014 at 19:36

10 votes

Constructions better than a random one.

answered Mar 15, 2011 at 0:27

8 votes

Integrality gap and approximation ratio

answered Feb 14, 2011 at 18:26

7 votes

Euclidean-squared max-cut in low dimensions

answered Mar 15, 2011 at 7:38

5 votes

Accepted

quasiP-Natural Property again SIZE($n^e$) for fixed e.

answered Feb 19, 2011 at 20:11

Stack Exchange Network

16 Answers

Hierarchy theorem for circuit size

Fourier coefficients Boolean Functions described by Bounded Depth Circuits with AND OR and XOR gates

Proving lower bounds by proving upper bounds

The importance of Integrality Gap

Subexponentially solvable hard graph problems

Non-Uniform vs. Uniform Adversaries

Simple Constructions of Special Graph Families

Do runtimes for P require EXP resources to upper-bound? … are concrete examples known? (answer: yes and yes)

Computing any information about Max-3SAT

Is MAX CUT approximation resistant?

Bounded-cardinality bounded-frequency set cover: hardness of approximation

Existence of long induced paths in expander graphs

Constructions better than a random one.

Integrality gap and approximation ratio

Euclidean-squared max-cut in low dimensions

quasiP-Natural Property again SIZE($n^e$) for fixed e.