Noam's user avatar
Noam's user avatar
Noam's user avatar
Noam
  • Member for 13 years, 8 months
  • Last seen more than 2 years ago
73 votes

Advice on good research practices

56 votes

How to get a job

44 votes
Accepted

For which algorithms is there a large gap between the theoretical analysis and reality?

40 votes

Algorithms from the Book

38 votes
Accepted

Many-one reductions vs. Turing reductions to define NPC

34 votes
Accepted

How to produce a random graph that does not have a Hamiltonian cycle?

32 votes
Accepted

Does NP-hardness imply P-hardness?

29 votes
Accepted

Evidence that PPAD is hard?

29 votes
Accepted

What are the consequences of Parity-L = P?

28 votes
Accepted

Interactive proofs for levels of the polynomial hierarchy

24 votes
Accepted

Computable function $f = \Theta(g)$ with $g$ uncomputable

23 votes

Inspirational talk for final year high school pupils

23 votes
Accepted

Optimization problems with minimax characterization, but no polynomial-time algorithm

22 votes
Accepted

Running a BPP algorithm with a half-random, half-adversarial string

22 votes
Accepted

Communication Complexity ...Classes?

22 votes
Accepted

Separating Logspace from Polynomial time

22 votes

Higher-order algorithms

21 votes
Accepted

What is the motivation behind the definition of pseudorandom in Nisan/Wigderson?

20 votes
Accepted

Does There exist a particular PSPACE Complete Problem which has a FPTAS algorithm?

19 votes
Accepted

Sum-of-square-roots-hard problems?

19 votes

Efficient and simple randomized algorithms where determinism is difficult

19 votes
Accepted

Parity-L vs. NL

18 votes
Accepted

Does Nisan's pseudo-random generator relativize?

17 votes
Accepted

multi-party Communication complexity of "Set Partition problem"

17 votes

AM/MA and NP in analogy to P and BPP

16 votes

Inspirational talk for final year high school pupils

15 votes
Accepted

What evidence is there that $coRP \neq NP$?

15 votes

Algorithmic game theory - nonstandard equilibrium concepts?

14 votes

Can a nondeterministic finite automata (NDFA) be efficiently converted to a deterministic finite automata (DFA) in subexponential space/time?

14 votes
Accepted

What specific evidence is there for P = RP?