Theoretical Computer Science

Revival

 Revival
Answer more than 30 days after a question was asked as first answer scoring 2 or more. This badge can be awarded multiple times.
Awarded 632 times.
Separating words with random DFAs
Awarded Jun 24, 2021 at 20:20
Maximum cliques of the transitive closure of a chordal DAG
Awarded May 20, 2021 at 9:27
Are there problems in $DTIME(n^k) - DTIME(n^{k-1})$ that are not hard for $DTIME(n^{k-1})$ under nearly linear time reductions?
Awarded May 18, 2021 at 14:26
Family of functions with properties similar to k-wise independent hash functions
Awarded Apr 30, 2021 at 20:17
$RL=L$ Progress Since 2006
Awarded Apr 27, 2021 at 22:06
Complexity of unique coloring of graphs
Awarded Apr 21, 2021 at 21:26
Why semi-gradient is used instead of the true gradient in Q-learning?
Awarded Apr 14, 2021 at 4:46
Complete axiomatization of relation algebras without ${}^-$ and $\top$
Awarded Apr 12, 2021 at 14:12
Why Reflexive Graphs for Parametricity?
Awarded Mar 23, 2021 at 0:42
An optimization problem
Awarded Mar 1, 2021 at 20:48
Is there any second-order logic finite satisfiability checker?
Awarded Feb 25, 2021 at 20:31
Languages whose Parikh image is recognizable
Awarded Feb 22, 2021 at 22:47
Algorithms for graph generation given parameters
Awarded Feb 18, 2021 at 12:50
NEXPTIME-completeness with more time for reductions
Awarded Feb 11, 2021 at 13:04
Count $k$-hop neighborhood for every vertex
Awarded Feb 2, 2021 at 21:05
Reversible Turing tarpits?
Awarded Jan 20, 2021 at 9:22
Analogue of $k$-wise independence for other distributions than uniform
Awarded Jan 3, 2021 at 9:25
Noisy channel coding theorem in quantum information
Awarded Jan 2, 2021 at 19:48
Highway dimension
Awarded Dec 13, 2020 at 13:10
Bounds on this Strategy for Separating Words
Awarded Nov 14, 2020 at 8:03
Partitioning a square for optimal queries
Awarded Nov 13, 2020 at 16:25
Reducing Parameterized Problems (whose solution size can be "large") to W[i]-complete problems (for fixed i)
Awarded Nov 12, 2020 at 16:41
Is this a known learning problem?
Awarded Oct 29, 2020 at 20:47
Algebraic topology for termination proofs
Awarded Sep 24, 2020 at 8:50
Reducing the Height of Context-Free Grammars
Awarded Aug 2, 2020 at 17:12
Rewrite relations - proof of correctness
Awarded Aug 2, 2020 at 6:20
Counting words of length $n$ in an inherently ambiguous CFG?
Awarded Jul 17, 2020 at 5:19
Subsets of $\omega$-words which share certain factors and languages accepted by special (prefix-closed) automata
Awarded Jul 9, 2020 at 19:35
What are some example problems for integer programming that are *not binary*
Awarded Jun 21, 2020 at 14:34
Citation for isometric embeddability of $\ell_2$ into $\ell_p^\binom{n}{2}$ for $p \geq 1$?
Awarded Jun 13, 2020 at 18:41
Automatic theorem prover for first-order logic versus model checker
Awarded May 29, 2020 at 23:10
Witness verifiable quantum advantage
Awarded May 27, 2020 at 2:55
Approximation algorithms for multicut for special classes of graphs
Awarded May 1, 2020 at 3:25
Busy Beaver Equivalent for the Untyped Lambda Calculus
Awarded Apr 24, 2020 at 22:36
A game on several graphs
Awarded Apr 6, 2020 at 17:25
Generalization and instantiation of types in Hindley-Milner type inference
Awarded Mar 14, 2020 at 22:35
Infinite process balls in bins problem
Awarded Feb 10, 2020 at 12:15
The power of randomized logspace with two-way access to the random tape
Awarded Jan 31, 2020 at 16:20
Intersection of two deterministic parity automata
Awarded Jan 9, 2020 at 18:10
Bivariate low-degree polynomial testing of Polishchuk-Spielman
Awarded Dec 21, 2019 at 7:05
Best Hamiltonian Cycle Problem solver
Awarded Dec 21, 2019 at 2:25
Small kernel (i.e. proof-verifier) for Agda?
Awarded Dec 5, 2019 at 22:40
Maximum matching M with the condition G[M] is 2K_2-free
Awarded Nov 30, 2019 at 10:50
What is the fastest algorithm for calculating nth term of Fibonacci sequence?
Awarded Nov 12, 2019 at 12:30
Where does a C-like language without heaps belong in the automata hierarchy?
Awarded Nov 7, 2019 at 0:55
Evidence for $\mathsf{P} \neq \mathsf{PP}$ if the polynomial hierarchy collapses?
Awarded Oct 28, 2019 at 12:30
Arranging letters to make a word in a regular language
Awarded Oct 21, 2019 at 10:15
Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?
Awarded Oct 15, 2019 at 21:00
Does “Second X is NP-complete” imply “X is NP-complete”?
Awarded Oct 12, 2019 at 11:00
NP-intermediate approximation regimes for natural problems within the MAX-k-CSP family
Awarded Oct 9, 2019 at 19:30
Regularity Lemma for Sparse Graphs
Awarded Oct 1, 2019 at 21:15
What is the best approximation and exact algorithm for vertex cover on cubic graphs?
Awarded Sep 15, 2019 at 1:45
Complexity of DFA intersection in this specific case?
Awarded Sep 10, 2019 at 16:55
Complexity of #PP2DNF where we also count on the number of clauses
Awarded Aug 21, 2019 at 16:00
Can reciprocal inputs speed up monotone computations?
Awarded Aug 15, 2019 at 8:15
References on generalization bounds
Awarded Jul 15, 2019 at 7:20
Looking for reference on NP-Completeness of proofs of length n
Awarded Jun 30, 2019 at 5:45
What is the maximal load of a "latency-bounded" Cuckoo Hash?
Awarded Jun 24, 2019 at 20:20
Can three stacks be implemented in one array, with O(1) push/pop time?
Awarded Jun 12, 2019 at 8:15
Why is counting the number of hamiltonian subgraphs $\sharp P $ hard?
Awarded May 24, 2019 at 19:35
1
2
3 4 5
…
11

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.