Skip to main content
Share Your Experience: Take the 2024 Developer Survey
Ross Snider's user avatar
Ross Snider's user avatar
Ross Snider's user avatar
Ross Snider
  • Member for 13 years, 9 months
  • Last seen more than 6 years ago
30 votes
6 answers
1k views

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

27 votes
2 answers
1k views

Complexity of Topological Properties.

22 votes
2 answers
1k views

How does the Mulmuley-Sohoni geometric approach to producing lower bounds avoid producing natural proofs (in the Razborov-Rudich sense)?

13 votes
1 answer
594 views

What languages have been successfully cryptographically trapdoored?

10 votes
2 answers
480 views

Do good PCPs for NP give us good PCPs for the entire polynomial hierarchy?

5 votes
1 answer
1k views

Computational complexity of modular power towers (tetration)

3 votes
0 answers
95 views

Closest Vector Problem with sparse basis and target vector

2 votes
0 answers
270 views

Some problems involving polynomials of public and private variables over GF(2).

1 vote
0 answers
100 views

Nearly-uniformally sampling lattice points from a basis that lie on the interior of a polytope