Daniel Apon's user avatar
Daniel Apon's user avatar
Daniel Apon's user avatar
Daniel Apon
  • Member for 13 years, 8 months
  • Last seen more than 6 years ago
  • Berkeley, CA, United States
63 votes

What papers should everyone read?

57 votes

Major unsolved problems in theoretical computer science?

41 votes
Accepted

What are good references to understanding the proof of the PCP theorem?

30 votes
Accepted

Hierarchies in NP (under the assumption that P != NP)

26 votes

Ways for a mathematician to stay informed of current research in complexity theory

24 votes

Advice on good research practices

22 votes
Accepted

What's the difference between the Actor Model of Concurrency and Communicating Sequential Processes

22 votes

What would be the consequences of factoring being NP-complete?

21 votes
Accepted

Consequences of Complete problems for NP intersects coNP

21 votes

Easy decision problem, hard search problem

16 votes
Accepted

What evidence do we have for (and against) Unique Games Conjecture?

13 votes

Complexity Classes for Cases Other Than "Worst Case"

12 votes
Accepted

Integer Factoring via Lattice Reduction?

11 votes

Proving lower bounds by proving upper bounds

11 votes

Examples in which the size of the alphabet ($\geq 2$) used for an encoding matters

10 votes
Accepted

Is #P contained in PSPACE?

10 votes

Can strong NP-hardness really be shown using plain polytime reductions?

9 votes

What would it mean to disprove Church-Turing thesis?

8 votes

Using error-correcting codes in theory

8 votes

PCP characterization of NP

8 votes

Applications of Complexity Theory

8 votes
Accepted

Learning with (Signed) Errors

8 votes

Evidence that PPAD is hard?

7 votes
Accepted

What is a multicast graph?

6 votes

FNP complexity class

6 votes
Accepted

Why is the security of lattice cryptosystems not provable from $P \neq NP$?

6 votes
Accepted

How and why does Recrypt function work?

5 votes
Accepted

Subset Sum bounds

5 votes

Easy problems with hard counting versions

5 votes
Accepted

Time complexity of Held-Karp algorithm for TSP