Theoretical Computer Science

Nice Answer

 Nice Answer
Answer score of 10 or more. This badge can be awarded multiple times.

earned this badge 117 times.
Oblivious Turing Machine emulation lower bound
Awarded Mar 12, 2012 at 18:26
Characterization of problems for which sublinear time algorithms exist
Awarded Mar 8, 2012 at 5:43
When are two algorithms said to be "similar"?
Awarded Mar 6, 2012 at 18:09
Solving $n$-SAT and #$n$-SAT
Awarded Feb 25, 2012 at 0:31
Are quasi-polynomial sized circuits for 3-SAT trivial?
Awarded Jan 10, 2012 at 8:38
Super-polynomial time approximation algorithms for MAX 3SAT
Awarded Dec 9, 2011 at 0:09
How many tautologies are there?
Awarded Nov 21, 2011 at 16:25
Uses of XORification
Awarded Nov 17, 2011 at 12:33
What are the consequences of $L = \oplus L$?
Awarded Nov 17, 2011 at 1:22
Toy examples for barriers to $P \ne NP$
Awarded Nov 10, 2011 at 12:57
(False?) proof for computability of a function?
Awarded Oct 30, 2011 at 17:43
Results showing existence/non-existence of finite graphs with specific computable properties imply certain complexity results
Awarded Oct 12, 2011 at 16:31
NP-complete variants of undecidable problems?
Awarded Sep 16, 2011 at 19:34
Problems outside of P that are not P-hard
Awarded Sep 1, 2011 at 14:30
Fast sparse boolean matrix product with possible preprocessing
Awarded Aug 30, 2011 at 14:57
How Hard is Exact Simulation of Algorithms, and a Related Operation on Complexity Classes
Awarded Aug 25, 2011 at 7:32
A data structure for minimum dot product queries
Awarded Aug 16, 2011 at 14:05
Complexity of Unique s-t-Connectivity
Awarded Aug 12, 2011 at 2:27
What hierarchies and/or hierarchy theorems do you know?
Awarded Jul 25, 2011 at 18:27
NTIME(n^k) ≠ DTIME(n^k) ?
Awarded Jul 13, 2011 at 3:03
Paradigms for complexity analysis of algorithms
Awarded Jul 3, 2011 at 7:05
What is the big version of NC?
Awarded May 27, 2011 at 21:24
Hierarchy for BPP vs derandomization
Awarded May 27, 2011 at 20:19
Is there any justification to believe that $NL\neq L$?
Awarded Mar 12, 2011 at 4:51
Are $PSPACE$-complete problems inherently less tractable than $NP$-complete problems?
Awarded Mar 8, 2011 at 3:38
Is there a Time Hierarchy theorem for PH?
Awarded Feb 14, 2011 at 19:49
How do you get a "Physical Intuition" for results in TCS?
Awarded Feb 9, 2011 at 2:58
Techniques for Reversing the Order of Quantifiers
Awarded Jan 23, 2011 at 19:18
Highest lower bound on NP problems (TSP)
Awarded Jan 18, 2011 at 15:57
Finding a 5-cycle in a sparse graph efficiently.
Awarded Dec 17, 2010 at 1:48
Matrix multiplication in $O(n^2 \log n)$
Awarded Nov 28, 2010 at 0:50
Open problems on the frontiers of TCS
Awarded Nov 15, 2010 at 14:53
Open problems on the frontiers of TCS
Awarded Nov 11, 2010 at 1:49
Rigour leading to insight
Awarded Nov 5, 2010 at 0:33
Examples of the price of abstraction?
Awarded Nov 4, 2010 at 14:28
Examples of "Unrelated" Mathematics Playing a Fundamental Role in TCS?
Awarded Oct 26, 2010 at 9:41
Inspirational talk for final year high school pupils
Awarded Oct 23, 2010 at 18:17
Hardness of approximation assuming NP != coNP
Awarded Oct 22, 2010 at 0:57
Optimal greedy algorithms for NP-hard problems
Awarded Oct 21, 2010 at 8:51
True Bit Complexity of matrix multiplication is $O(n^{4})$
Awarded Oct 21, 2010 at 7:31
Permanents - Approximation and connection to integer factorization
Awarded Oct 21, 2010 at 5:41
NC = P consequences?
Awarded Oct 8, 2010 at 2:40
Is $AC^0/poly \cap NP$ contained in $P$?
Awarded Oct 7, 2010 at 0:05
Chernoff-type Inequality for pair-wise independent random variables
Awarded Oct 6, 2010 at 17:45
DFA intersection in subquadratic space?
Awarded Oct 2, 2010 at 9:34
Are there alternatives to using polynomials in defining the different notions of efficient computation?
Awarded Sep 25, 2010 at 14:38
Space complexity of Coppersmith–Winograd algorithm
Awarded Sep 15, 2010 at 9:47
Problems that can be used to show polynomial-time hardness results
Awarded Sep 14, 2010 at 16:26
Semantic vs. Syntactic Complexity Classes
Awarded Sep 13, 2010 at 13:16
What papers should everyone read?
Awarded Sep 13, 2010 at 1:41
References for TCS proof techniques
Awarded Sep 11, 2010 at 5:07
Lower bounds on #SAT?
Awarded Sep 9, 2010 at 12:30
Do all complexity classes have a leaf language characterization?
Awarded Aug 30, 2010 at 18:19
Is there a complexity theory analogue of Rice's theorem in computability theory?
Awarded Aug 30, 2010 at 2:04
What are the best known upper bounds and lower bounds for computing O(log n)-Clique?
Awarded Aug 29, 2010 at 18:43
Where and how did computers help prove a theorem?
Awarded Aug 24, 2010 at 1:57
What are the best current lower bounds on 3SAT?
Awarded Aug 17, 2010 at 14:49
1
2

Others with this badge

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.