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.
Minimum distance of a code
Awarded May 4, 2019 at 0:05
Resources for Church's paper "An Unsolvable Problem of Elementary Number Theory"?
Awarded Apr 29, 2019 at 19:35
Are there any implementations of a graph crossing algorithm?
Awarded Apr 24, 2019 at 9:20
Does 1-in-3 SAT remain NP-hard even if every variable occurs both positively and negatively?
Awarded Apr 15, 2019 at 7:40
About the position of side conditions in an inference rule
Awarded Apr 11, 2019 at 22:30
Möbius values of CNF and DNF lattices of a monotone Boolean function
Awarded Apr 2, 2019 at 6:30
VC dimension of intersection of half-spaces
Awarded Mar 6, 2019 at 10:15
How to deal with concept classes with exponential value of VC dimension
Awarded Mar 6, 2019 at 8:55
Bounded distance decoding beyond Babai
Awarded Feb 26, 2019 at 17:25
Smoothed analysis to compare algorithms
Awarded Feb 14, 2019 at 11:40
How to start learning formal language theory
Awarded Jan 24, 2019 at 19:15
Optimal evaluation of polynomials / rational functions
Awarded Jan 10, 2019 at 9:55
how to achieve a topological sort of an given sequence with minimum swaps
Awarded Jan 7, 2019 at 12:15
Why Tomita created GLR and didn't use Earley?
Awarded Nov 1, 2018 at 18:35
Is there any research on approximation of reals with computable numbers
Awarded Oct 30, 2018 at 10:35
What are bounded-treewidth circuits good for?
Awarded Oct 29, 2018 at 17:20
What is the Quantum Cheshire Cat experiments' import to Quantum Computing?
Awarded Oct 25, 2018 at 21:30
An upper bound for chi-square divergence in terms of KL divergence for general alphabets
Awarded Oct 23, 2018 at 0:35
State of research on SHA-1 Collision Attacks
Awarded Oct 18, 2018 at 19:40
Explanation of polar decoding?
Awarded Oct 10, 2018 at 7:01
Complexity of finding a consistent hyperplane
Awarded Oct 7, 2018 at 16:35
Is deciding whether changing one entry decreases the permanent of a matrix in the polynomial hierarchy?
Awarded Oct 2, 2018 at 11:45
Set optimization problem - is it np-complete?
Awarded Oct 1, 2018 at 12:00
Is there a candidate for a post-quantum one-way group action?
Awarded Sep 24, 2018 at 17:00
Can boolean algebra be expressed in simply typed lambda caclulus?
Awarded Sep 24, 2018 at 13:30
"Verifiable information": is this a known concept?
Awarded Sep 23, 2018 at 16:50
Eilenberg's rational hierarchy of nonrational automata & languages -- where is it now?
Awarded Sep 20, 2018 at 8:15
Example demonstrating the power of non-deterministic circuits
Awarded Sep 9, 2018 at 20:50
If $u\cdot v \in (z \cdot z')^*$ and $v \cdot u \in (z' \cdot z)^*$ then $u \in (z \cdot z')^* \cdot z$
Awarded Sep 6, 2018 at 10:10
Which monotone Boolean functions are representable as thresholds on sums?
Awarded Sep 2, 2018 at 8:55
Is Church-pentation implementable in Agda?
Awarded Aug 31, 2018 at 7:30
Proof refutation: Amateur reviews of ambitious CoRR papers
Awarded Aug 30, 2018 at 15:30
Is the following optimization problem (another variant to a previous problem) NP-hard?
Awarded Aug 28, 2018 at 6:05
Fast Finding Main Diagonal of Matrix Multiplication
Awarded Aug 22, 2018 at 17:50
Is this "subgroup packing" polytope integral?
Awarded Aug 20, 2018 at 5:25
If I naively generalize the homeomorphic embedding relation for labeled finite trees in this way, do I still have a wqo?
Awarded Aug 16, 2018 at 15:45
Is there higher-dimensional generative grammar?
Awarded Aug 1, 2018 at 20:55
A simple(?) funny combinatorial problem!
Awarded Jul 30, 2018 at 19:02
Complexity of finding semi-ordered Eulerian tours in a 4-regular graph
Awarded Jul 25, 2018 at 8:01
How to determine whether a proof requires "higher-order reasoning techniques"?
Awarded Jul 19, 2018 at 9:22
What are theoretical computer science jobs?
Awarded Jul 17, 2018 at 5:53
Functional Completeness of 3-valued logic
Awarded Jul 7, 2018 at 15:50
Papers on using resource states to implement QFT efficiently
Awarded Jul 6, 2018 at 17:39
Graph rewriting with one-to-many pattern matching?
Awarded Jul 6, 2018 at 17:08
Sparsification Lemma for k-SAT and Exponential Time Hypothesis
Awarded Jun 23, 2018 at 23:46
Is equivalence of unambiguous context-free languages decidable?
Awarded Jun 15, 2018 at 11:15
complexity of a constraint satisfaction promise problem
Awarded Jun 6, 2018 at 14:15
Autoencoders and information compression
Awarded May 27, 2018 at 22:01
What makes a language (and its type-system) capable of proving theorems about its own terms?
Awarded May 24, 2018 at 15:08
Avoiding Cycles with Unification and Subtyping
Awarded May 22, 2018 at 21:14
Can Quarter-Subset Membership be decided space-efficiently?
Awarded May 17, 2018 at 23:09
Generalization of Dilworth's theorem for labeled DAGs
Awarded May 8, 2018 at 16:29
Improving Bloom filter - can we distinguish elements of a database using less than 2.33275 bits/element?
Awarded May 7, 2018 at 14:09
P/Poly vs Uniform Complexity Classes
Awarded May 4, 2018 at 21:15
Can one prove the discovery of a P versus NP solution without actually revealing it?
Awarded Apr 13, 2018 at 19:12
List of (unsolved) complexity problems arising from PL
Awarded Apr 11, 2018 at 15:14
Complexity of finding a consistent hyperplane
Awarded Apr 9, 2018 at 22:31
Are single hidden-layered neural networks at least as good as multi hidden-layered neural networks?
Awarded Mar 24, 2018 at 10:48
Converting Kuroda normal form rules to the Penttonen normal form
Awarded Mar 21, 2018 at 22:40
Benefits for syntactic and semantic classes
Awarded Mar 10, 2018 at 21:34
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.