Skip to main content
Share Your Experience: Take the 2024 Developer Survey
Manu's user avatar
Manu's user avatar
Manu's user avatar
Manu
  • Member for 13 years, 9 months
  • Last seen this week
93 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)$?

16 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

Small steps for better TCS conferences?

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
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?