Skip to main content
Share Your Experience: Take the 2024 Developer Survey
Andras Farago's user avatar
Andras Farago's user avatar
Andras Farago's user avatar
Andras Farago
  • Member for 11 years, 6 months
  • Last seen more than a month ago
22 votes

Is NP in $DTIME(n^{poly\log n})$?

22 votes
Accepted

Why is the "balanced vs constant function" problem not a proof that P ≠ BPP?

18 votes

Which randomized algorithms have exponentially small error probability?

16 votes

Easy to optimize but hard to evaluate

13 votes

Consequences of $NP=coNP$ and $P\ne NP$?

12 votes

Problems that are easy on unweighted graphs, but hard for weighted graphs

11 votes
Accepted

Evidence that Graph Isomorphism problem is not $NP$-complete

8 votes
Accepted

Complexity of finding an edge set yielding specified vertex degrees

8 votes
Accepted

Complexity class of optimization problems whose fractional relaxation is polynomial-time solvable

8 votes
Accepted

Completeness under injective Karp reductions

8 votes

Natural NP-complete problems with "large" witnesses

7 votes

Natural graphs that are not scale free

7 votes

Common false beliefs in theoretical computer science

5 votes

Examples of the value of proofs for algorithms

5 votes
Accepted

Relationship between Random Graph Theory and TCS

5 votes

Hard-looking algorithmic problems made easy by theorems

5 votes

A curious asymmetry in good characterizations

5 votes

"Almost easy" NP-complete problems

4 votes
Accepted

Partitioning the edges of a complete graph into smaller complete graphs

4 votes

Is there a computing problem which is in quasi-polynomial time but is (maybe) not in $\beta P$?

4 votes

Complexity of sampling a clique uniformly at random

3 votes
Accepted

Does P^NP=NP imply NP=coNP?

3 votes

Is it right to ask a TCS researcher about the real life application of the problem she/he is working on?

3 votes

Nontrivial membership in NP

3 votes

What would be the consequences of PH=PSPACE?

2 votes

Complexity class separations without hierarchy theorems

2 votes

Why are so few natural candidates for NP-intermediate status?

2 votes

Hard-looking algorithmic problems made easy by theorems

2 votes

Relationship between Random Graph Theory and TCS

2 votes

Theoretical explanations for practical success of SAT solvers?