Kaveh's user avatar
Kaveh's user avatar
Kaveh's user avatar
Kaveh
  • Member for 13 years, 6 months
  • Last seen this week
124 votes
13 answers
13k views

Advice on good research practices

49 votes
8 answers
9k views

The importance of Integrality Gap

43 votes
3 answers
4k views

What are the reasons that researchers in computational geometry prefer the BSS/real-RAM model?

36 votes
1 answer
3k views

Consequences of $\mathsf{NP}$ containing $\mathsf{BPP}$

34 votes
3 answers
2k views

Is $AC^0/poly \cap NP$ contained in $P$?

30 votes
3 answers
2k views

Is there a candidate for a natural problem in $P/poly - P$?

30 votes
3 answers
2k views

Curry-Howard and programs from non-constructive proofs

24 votes
2 answers
895 views

What evidence do we have for (and against) Unique Games Conjecture?

24 votes
4 answers
2k views

Handbook of advanced data structures

23 votes
4 answers
1k views

Monotone arithmetic circuits

22 votes
1 answer
604 views

Does $\mathsf{P/poly}$ have subexponential-size bounded-depth circuits?

22 votes
3 answers
3k views

Why do we use single tape Turing machines for time complexity?

21 votes
0 answers
280 views

Descriptive complexity characterization of TimeSpace classes

21 votes
4 answers
502 views

Which results in complexity theory make essential use of uniformity?

20 votes
3 answers
1k views

Survey on algorithms/complexity of linear algebra

20 votes
11 answers
1k views

Models of random graphs, for real computer networks

19 votes
1 answer
703 views

Looking for a nice problem inside SC but not in the first two levels

19 votes
1 answer
762 views

Can we count in depth $\frac{\lg n}{\lg \lg n}$?

19 votes
22 answers
9k views

Which algorithms are used most often in practice?

18 votes
3 answers
592 views

Constructively efficient algorithms without efficient correctness and efficiency proof

16 votes
2 answers
939 views

Regular versus TC0

16 votes
1 answer
609 views

Do the proofs that permanent is not in uniform $\mathsf{TC^0}$ relativize?

15 votes
2 answers
752 views

Circuit Complexity Charaterization for DLogTime and NLogTime

15 votes
1 answer
898 views

Random monotone function

15 votes
1 answer
473 views

How efficient are DPLL-based SAT-solvers on satisfiable instances of PHP?

15 votes
1 answer
265 views

What is the minimum required depth of reductions for NP-hardness of SAT?

14 votes
1 answer
421 views

$\mathsf{NC^1}$ circuit evaluation

14 votes
3 answers
582 views

Nondeterministic speed-up of deterministic computation

14 votes
1 answer
2k views

What are the classic papers from the recursion theoretic area of complexity theory?

13 votes
4 answers
821 views

The origin of the terms "efficient" and "feasible" computation/algorithm