user avatar
user avatar
user avatar
Luca Trevisan
  • Member for 11 years, 11 months
  • Last seen more than 8 years ago
33 votes
Accepted

Hierarchy theorem for circuit size

31 votes
Accepted

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

24 votes
Accepted

Proving lower bounds by proving upper bounds

22 votes

The importance of Integrality Gap

20 votes
Accepted

Subexponentially solvable hard graph problems

16 votes
Accepted

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

16 votes
Accepted

Non-Uniform vs. Uniform Adversaries

16 votes
Accepted

Simple Constructions of Special Graph Families

14 votes

Computing any information about Max-3SAT

14 votes
Accepted

Is MAX CUT approximation resistant?

12 votes

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

10 votes

Constructions better than a random one.

10 votes
Accepted

Existence of long induced paths in expander graphs

8 votes

Integrality gap and approximation ratio

7 votes

Euclidean-squared max-cut in low dimensions

5 votes
Accepted

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