Theoretical Computer Science

Nice Question

 Nice Question
Question score of 10 or more. This badge can be awarded multiple times.
Awarded 2895 times.
Recent advances in computer science since 2010?
Awarded yesterday
FO-uniform AC0 with some predicate
Awarded 2 days ago
Does $NC=P$ imply the collapse of Polynomial Hierarchy?
Awarded Sep 19 at 21:18
Law of the Excluded Middle in complexity theory
Awarded Sep 12 at 16:12
Complexity of 1-or-3-in-3-SAT (odd-3-SAT)
Awarded Sep 6 at 5:50
What are examples of recent relatively simple 'toolbox algorithms'?
Awarded Aug 8 at 4:05
Complexity of a problem over acyclic context-free grammars
Awarded Aug 7 at 14:57
Quickly finding empty-string producing nonterminals in a CFG
Awarded Jul 31 at 14:03
Are there any 'graphical' algebras that can describe the 'shape' of graphs?
Awarded Jul 20 at 13:48
What is a very simple pseudodeterministic algorithm (for educational purposes)?
Awarded Jul 19 at 15:50
Is 4-in-a-row PSPACE-complete?
Awarded Jul 18 at 18:28
Computing the edge orbits of a graph (and discussing definitions)
Awarded Jul 18 at 16:08
NP-complete decision problems on deterministic automata
Awarded Jul 6 at 21:57
Formulating P vs NP without Turing machines
Awarded Jul 5 at 8:20
What is the "standard" lambda-calculus model for bicartesian closed categories?
Awarded Jul 5 at 5:58
General collection with the current state of complexity bounds of well-known unsolved problems?
Awarded Jul 4 at 19:26
Is there a problem in ZPP not yet in P?
Awarded Jul 4 at 13:42
Complexity results for Lower-Elementary Recursive Functions?
Awarded Jun 29 at 13:08
Does every Turing-recognizable undecidable language have a NP-complete subset?
Awarded Jun 29 at 0:43
Regular expressions without alternation
Awarded Jun 22 at 17:49
Regular languages and constant communication complexity
Awarded Jun 21 at 2:11
Proof for Kolmogorov complexity is uncomputable using reductions
Awarded Jun 12 at 18:06
Why is the "balanced vs constant function" problem not a proof that P ≠ BPP?
Awarded Jun 1 at 17:01
Where is the model theory in programming language theory?
Awarded May 22 at 20:06
Complexity of $(\Delta-1)$-coloring graphs of maximum degree $\Delta$
Awarded May 18 at 3:51
A simple proof that decidability of typability in System F ($\lambda 2$) implies decidability of type checking?
Awarded May 8 at 10:34
Is it NP-hard to find an order on a set of strings so that the concatenation is a given string?
Awarded Apr 29 at 21:36
Random unbalanced bipartite graphs are good small set expanders
Awarded Apr 23 at 6:34
Tree decomposition for planar graphs
Awarded Apr 21 at 8:47
Direct Proof that the Pigeonhole Principle is Hard for Regular Resolution
Awarded Apr 20 at 23:55
Combinatorics of a badminton tournament
Awarded Apr 18 at 9:36
Reducing #SAT to #MONOTONE-2SAT
Awarded Apr 15 at 10:57
Is convex optimisation in P?
Awarded Mar 25 at 8:30
Theoretical Computer Science vs other Sciences?
Awarded Mar 19 at 8:33
Is there a purely functional vector with O(1) access to the front and back but O(log n) concatenation?
Awarded Mar 17 at 15:56
What kind of theoretical object corresponds to a C++ concept?
Awarded Mar 4 at 3:05
What is higher-order in higher-order abstract syntax?
Awarded Feb 25 at 23:26
"Caged" complexity classes ?
Awarded Feb 11 at 15:06
Is this a known problem, and is it NP-complete?
Awarded Feb 8 at 4:03
Difference between Strict Consistency and Sequential Consistency
Awarded Feb 6 at 17:01
Can we do integer addition in linear time?
Awarded Jan 19 at 20:11
What is the difference between System F and Hindley-Milner type system?
Awarded Jan 13 at 5:36
Algebraic equivalent of SAT?
Awarded Jan 9 at 13:26
Explaining monad transformers in categorical terms
Awarded Dec 29, 2022 at 11:09
Functional Completeness of 3-valued logic
Awarded Dec 29, 2022 at 3:51
How do you decide when you have enough research results to write a paper and to which journal you submit the paper
Awarded Dec 25, 2022 at 8:26
Big gaps between RAM and Turing machine complexity
Awarded Dec 15, 2022 at 0:33
What is (a reasonable conjectured lower bound on) the query complexity of solving an $n\times n$ system of linear equations given space $O(n)$?
Awarded Dec 8, 2022 at 21:11
Maximizing sum edge weights
Awarded Dec 2, 2022 at 16:17
Vertex isoperimetric number of a graph - NP-hard?
Awarded Dec 2, 2022 at 14:35
Is the 3-coloring problem NP-hard on graphs of maximal degree 3?
Awarded Nov 22, 2022 at 19:09
True origin story of linear logic?
Awarded Nov 16, 2022 at 10:11
Why study type theory?
Awarded Nov 15, 2022 at 7:56
Induction-recursion in models other than $\mathbf{Set}$
Awarded Nov 9, 2022 at 0:25
Is there an efficient beta-equivalence algorithm?
Awarded Nov 3, 2022 at 10:26
Check whether DFA accepts majority of words less than a cutoff with another DFA
Awarded Oct 7, 2022 at 11:17
Expected number of random comparisons needed to sort a list
Awarded Oct 5, 2022 at 15:40
Any computable transcendental number that is computable in P time but not $O(n)$
Awarded Sep 19, 2022 at 23:41
Is uniform convergence faster for low-entropy distributions?
Awarded Sep 15, 2022 at 7:00
Hidden Constants in Complexity of Algorithms
Awarded Aug 27, 2022 at 15:37
1
2 3 4 5
…
49

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.