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.
Law of the Excluded Middle in complexity theory
Awarded Sep 21 at 20:56
What is the general consensus on the NL vs P question?
Awarded Jun 14 at 21:10
SC^2 algorithms for st-connectivity
Awarded Nov 26, 2022 at 8:05
Lower-bounds under SETH
Awarded Jun 26, 2022 at 22:02
Status of PP-completeness of MAJ3SAT
Awarded Jul 11, 2021 at 7:01
Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?
Awarded Nov 21, 2020 at 22:05
Complexity class of efficient streaming algorithms
Awarded May 4, 2020 at 0:40
If NP in BPP then NP equals RP
Awarded Dec 26, 2019 at 0:20
Complexity of k-clique for hypergraphs
Awarded Aug 26, 2019 at 19:40
Bootstrapping results that really bootstrap
Awarded Jul 12, 2019 at 22:15
An obstruction like ETH
Awarded Apr 30, 2019 at 19:30
Is there any book on the philosophical implications of Theoretical Computer Science?
Awarded Dec 9, 2017 at 8:48
Smallest vertex cover which is also an independent set
Awarded Oct 6, 2016 at 14:43
Collapses under the assumption that $NEXP\subseteq P/Poly$
Awarded Aug 24, 2016 at 20:45
Memory requirement for fast matrix multiplication
Awarded Aug 15, 2016 at 8:07
Is ALogTime != PH hard to prove (and unknown)?
Awarded May 10, 2016 at 1:02
On reducing the hardness of CNF-SAT to k-Clique
Awarded Mar 22, 2016 at 23:05
How is the MA version of SETH proven to be false?
Awarded Jan 20, 2016 at 9:02
Space-time tradeoff lower bounds
Awarded Nov 12, 2015 at 15:32
Potentially equal complexity classes without known contradictory relativizations
Awarded Nov 12, 2015 at 11:25
Does the isomorphism conjecture imply exponential lower bounds on witnesses density?
Awarded Nov 9, 2015 at 9:10
Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?
Awarded Nov 8, 2015 at 14:02
Complexity Classes for Cases Other Than "Worst Case"
Awarded Nov 2, 2015 at 10:17
Proof that circuit upper bounds for $E$ imply $P \neq NP$
Awarded Oct 16, 2015 at 12:33
Problems not known to be PSPACE-complete
Awarded Oct 14, 2015 at 4:53
smallest circuit size using XOR gates
Awarded Aug 15, 2015 at 12:54
Beigel-Tarui transformation of ACC cricuits
Awarded Jun 8, 2015 at 6:51
Alternate notion of complexity based on gap between brute-force and the best algorithm?
Awarded May 12, 2015 at 9:20
Additive combinatorics applications in algorithm design
Awarded Mar 13, 2015 at 3:29
The hardness of generating an instance of a problem that is harder than the complexity of the resulting problem
Awarded Mar 9, 2015 at 17:46
Scope of natural proofs barrier
Awarded Mar 5, 2015 at 23:06
Problems with big open complexity gaps
Awarded Feb 27, 2015 at 21:55
$NP$-complete problem with quasi-polynomial bound on the number of solutions
Awarded Jan 7, 2015 at 19:14
Proofs, Barriers and P vs NP
Awarded Oct 27, 2014 at 14:46
MAX 1 in 2 SAT Algorithm
Awarded Aug 23, 2014 at 10:57
Arguments for/against Kolmogorov's conjecture about the circuit complexity of P
Awarded May 12, 2014 at 7:49
Testing boolean vectors orthogonality with fast query-time
Awarded Mar 9, 2014 at 4:52
Advanced techniques for determining complexity lower bounds
Awarded Mar 9, 2014 at 4:02
What would be the consequences of PH=PSPACE?
Awarded Feb 24, 2014 at 1:38
What is the most general structure on which matrix product verification can be done in $O(n^2)$ time?
Awarded Feb 19, 2014 at 19:47
Generalized Ladner's Theorem
Awarded Dec 19, 2013 at 16:20
Computational Model in SETH
Awarded Dec 2, 2013 at 12:40
Barriers to separating other complexity classes
Awarded Oct 9, 2013 at 12:47
Hardness of a subcase of Set Cover
Awarded Sep 6, 2013 at 4:40
Books/Lecture Notes on Parametrized Complexity
Awarded May 23, 2013 at 22:10
Introduction to spectral graph theory
Awarded May 20, 2013 at 12:05
What is the fastest known simulation of BPP using Las Vegas algorithms?
Awarded Apr 2, 2013 at 17:02
Can one return to a TCS research job after an excursion to a non-research industry job?
Awarded Mar 7, 2013 at 6:31
Do the proofs that permanent is not in uniform $\mathsf{TC^0}$ relativize?
Awarded Jan 11, 2013 at 5:47
Are there natural separations in the nondeterministic time hierarchy?
Awarded Jan 9, 2013 at 4:59
Consequences of $\mathsf{NP}$ containing $\mathsf{BPP}$
Awarded Jan 7, 2013 at 12:19
Constructivity in Natural Proof and Geometric Complexity
Awarded Jan 6, 2013 at 2:16
Succinct Problems in $\mathsf{P}$
Awarded Dec 16, 2012 at 21:53
Complexity class associated with exhaustive search
Awarded Nov 22, 2012 at 4:14
Implications of proof of abc conjecture for cs theory
Awarded Sep 27, 2012 at 9:07
Consequences of a $O^*(2^{n / \log(n \log n)} )$ algorithm for a #P-complete problem
Awarded Sep 11, 2012 at 11:31
Is "Experimental Complexity Theory" being used to solve open problems?
Awarded Jul 26, 2012 at 5:30
What is $\mathsf{NP}$ restricted to linear size witnesses?
Awarded May 10, 2012 at 4:35
How to compute powers of square matrices?
Awarded Apr 13, 2012 at 19:53
Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?
Awarded Mar 25, 2012 at 17:44
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.