user avatar
user avatar
user avatar
Manu
  • Member for 11 years, 10 months
  • Last seen more than a week ago
89 votes
Accepted

Are runtime bounds in P decidable? (answer: no)

26 votes

Techniques for Reversing the Order of Quantifiers

19 votes

Applications of TCS to classical mathematics?

17 votes
Accepted

Best known joint containments for/by NP and Parity-P?

17 votes
Accepted

Simplest proof of NP-completeness

17 votes
Accepted

$\overline{SAT} \in NTIME(subexp)$?

15 votes
Accepted

On fooling $AC^0$

14 votes

What is the most efficient way to generate a random permutation from probabilistic pairwise swaps?

12 votes

Algorithms from the Book.

12 votes
Accepted

The Examiner's Problem (uniform generation of SAT decision instances/answers)

11 votes
Accepted

One-way functions with respect to various resource bounds

11 votes
Accepted

Good seating arrangements for sequence of meals and tables of size k for a group of people

11 votes
Accepted

Algorithm to find shortest path from a set of nodes to another set of nodes?

11 votes

Small steps for better TCS conferences?

11 votes
Accepted

Fooling arbitrary symmetric functions

10 votes

Pseudorandom generator for finite automata

8 votes

Small steps for better TCS conferences?

8 votes

Difference between theory and practice of security and cryptography?

7 votes
Accepted

What are the different notions of one-way functions?

7 votes

Testing for positivity instead of equality

6 votes

Major unsolved problems in theoretical computer science?

6 votes

What hierarchies and/or hierarchy theorems do you know?

5 votes

Which complexity class does this number theory problem belong to?

5 votes

Additive combinatorics applications in algorithm design

4 votes

Classes of boolean functions where reasonable lower bounds on approximate degree is unknown?

4 votes

Size hierachy for uniform circuits

4 votes

Viola's Reduction of 3XOR to listing triangles

2 votes

Publishing short and simple results

1 vote

Is the the spectral norm of a Boolean function bounded by the degree of its Fourier expansion?

-1 votes

Small steps for better TCS conferences?