Lance Fortnow's user avatar
Lance Fortnow's user avatar
Lance Fortnow's user avatar
Lance Fortnow
  • Member for 12 years, 1 month
  • Last seen more than a month ago
63 votes

Single author papers against my advisor's will?

56 votes
Accepted

Why do we consider log-space as a model of efficient computation (instead of polylog-space) ?

36 votes

Are $PSPACE$-complete problems inherently less tractable than $NP$-complete problems?

33 votes
Accepted

Are there "NP-Intermediate-Complete" problems?

32 votes
Accepted

Derandomizing Valiant-Vazirani?

26 votes
Accepted

Is there an oracle such that SAT is not infinitely often in sub-exponential time?

23 votes

Is $PH \subseteq PP$?

20 votes

Hierarchy for BPP vs derandomization

19 votes

Proofs that expose a deeper structure

19 votes
Accepted

Circuits with oracles vs. Turing Machines with oracles

19 votes
Accepted

Complexity theory when an oracle is part of the input

18 votes
Accepted

Oracle relative to which $\mathsf{BPP}$ is not contained in $Δ_2 \mathsf{P}$

18 votes

A fixed-depth characterization of $TC^0$? $NC^1$?

17 votes

Is Norbert Blum's 2017 proof that $P \ne NP$ correct?

16 votes
Accepted

Is $P^{NPI}$ different from $P^{NP}$?

16 votes
Accepted

Natural candidates for NP-E and E-NP

16 votes

Examples of successful derandomization from BPP to P

15 votes
Accepted

Does diagonalization captures the essence of class separation ?

13 votes
Accepted

How can I show a Gap-P problem is outside #P

13 votes

Do the undecidable attributes of P pose an obstruction to deciding P versus NP? (answer: maybe)

13 votes

What is the "right" definition of upper and lower bounds?

13 votes

How are proofs verified probabilistically in interactive proof systems?

13 votes

Is Parity-P contained in PP?

12 votes
Accepted

Example of something that’s different for generic and random oracles?

12 votes
Accepted

$\mathsf{UPH}$, $\Pi_2^{\mathsf{P}}$ and $\mathsf{PP}$

12 votes
Accepted

Is $PP^{(PP^A)} = PP^A$ ?

11 votes
Accepted

Equilibrium in a Halting Game

11 votes

More on PH in PP?

11 votes
Accepted

Reduction from SAT to 0,1 integer linear program with zero or one solutions

11 votes

"Berman-Hartmanis Conjecture Separates NP From All Super-Poly. DTIME Classes" -- Worthy of arXiv.org?