Iddo Tzameret's user avatar
Iddo Tzameret's user avatar
Iddo Tzameret's user avatar
Iddo Tzameret
  • Member for 13 years, 6 months
  • Last seen more than a month ago
42 votes

Major unsolved problems in theoretical computer science?

25 votes

Does $VP \neq VNP$ imply $P \neq NP$?

23 votes

Using lambda calculus to derive time complexity?

22 votes
Accepted

Well known classes of boolean formulas that require exponentially long resolution proofs

21 votes

Which interesting theorems in TCS rely on the Axiom of Choice? (Or alternatively, the Axiom of Determinacy?)

14 votes

Formal representation of rings in computations

13 votes

Start learning proof complexity

12 votes
Accepted

$\mathsf{NC^1}$ circuit evaluation

12 votes

Conditions for tractability of 3SAT-Satisfiability

10 votes

Statements that imply $\mathbf{P}\neq \mathbf{NP}$

10 votes

Evaluating symmetric polynomials

9 votes

Forcing method used in Baker-Gill-Solovay Relativization paper and Cohen's Proof of Continuum Hypothesis Independence

8 votes

Lower bounds for noncommutative arithmetic circuits with exact division?

6 votes

Graph theoretic restriction to Proofs in Proof Complexity Theory

1 vote

Resolution vs Nondeterministic Search Problems