Andras Farago's user avatar
Andras Farago's user avatar
Andras Farago's user avatar
Andras Farago
  • Member for 11 years, 4 months
  • Last seen more than a month ago
1 vote

What are the consequences of $BPP \neq P$?

1 vote

Structural Complexity Theory References

22 votes
Accepted

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

8 votes
Accepted

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

4 votes

Complexity of sampling a clique uniformly at random

1 vote

Polynomially solvable 3-SAT problem instances

2 votes
Accepted

Hardness assumption: an NP-complete problem whose ratio of hard instances do not tend to zero?

7 votes

Common false beliefs in theoretical computer science

3 votes

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

2 votes

Relationship between Random Graph Theory and TCS

5 votes
Accepted

Relationship between Random Graph Theory and TCS

2 votes

Theoretical explanations for practical success of SAT solvers?

5 votes

Examples of the value of proofs for algorithms

8 votes
Accepted

Complexity of finding an edge set yielding specified vertex degrees

3 votes
Accepted

Does P^NP=NP imply NP=coNP?

1 vote

Hardness jumps in computational complexity?

4 votes

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

11 votes
Accepted

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

5 votes

"Almost easy" NP-complete problems

16 votes

Easy to optimize but hard to evaluate

1 vote

Natural NP-complete problems with "large" witnesses

8 votes
Accepted

Completeness under injective Karp reductions

18 votes

Which randomized algorithms have exponentially small error probability?

4 votes
Accepted

Partitioning the edges of a complete graph into smaller complete graphs

8 votes

Natural NP-complete problems with "large" witnesses

5 votes

A curious asymmetry in good characterizations

22 votes

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

2 votes

Complexity class separations without hierarchy theorems

3 votes

What would be the consequences of PH=PSPACE?

12 votes

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