Theoretical Computer Science

Editor

 Editor
First edit.
Awarded 3993 times.
Can equations be used to transmit large amounts of information instead of directly sending it?
Awarded 9 hours ago
What's the logical counterpart to jumps with arguments on CPS terms?
Awarded Jan 13 at 21:57
What type of Problems (Class and types) Can Be Solved Effectively with Quantum Computers?
Awarded Jan 12 at 21:18
What's the logical counterpart to jumps with arguments on CPS terms?
Awarded Jan 12 at 8:04
For which type systems have normalizaton proofs been formalized?
Awarded Jan 11 at 23:42
Split a string of positive numbers into substrings with decreasing totals
Awarded Jan 10 at 18:16
How to show that Color Tiles is NP-Complete
Awarded Jan 6 at 14:56
(post deleted or otherwise unavailable)
Awarded Jan 5 at 21:41
Randomized algorithms not based on Schwartz-Zippel
Awarded Jan 4 at 6:55
(post deleted or otherwise unavailable)
Awarded Dec 29 '21 at 16:51
equivalence between Bayesian prior distribution and regularization metric?
Awarded Dec 28 '21 at 23:27
Why is "topological sorting" topological?
Awarded Dec 26 '21 at 20:42
Turing meta-oracle
Awarded Dec 26 '21 at 12:10
Is this a variant of the set cover problem?
Awarded Dec 22 '21 at 13:05
Alternative to LBA for recognising context-sensitive languages
Awarded Dec 21 '21 at 22:06
How many bits are required to sample an almost pairwise independent hash function?
Awarded Dec 21 '21 at 12:15
Is the following graph an expander graph?
Awarded Dec 20 '21 at 21:36
(post deleted or otherwise unavailable)
Awarded Dec 20 '21 at 16:35
Set cover with rewards
Awarded Dec 20 '21 at 15:31
Regex: Pre-determining the position of matching characters
Awarded Dec 19 '21 at 9:17
Query in the proof of greedy manipulation theorem (of a voting scheme)
Awarded Dec 15 '21 at 8:31
Algorithm for finding traffic equilibrium
Awarded Dec 8 '21 at 22:21
Probability distributions generated by pushdown automata
Awarded Dec 6 '21 at 12:41
(post deleted or otherwise unavailable)
Awarded Dec 6 '21 at 9:18
Reference request for linear algebra over GF(2)
Awarded Dec 4 '21 at 20:42
(post deleted or otherwise unavailable)
Awarded Dec 1 '21 at 9:52
Properties of the polymorphic type $\Pi t : * . ((t \to t) \to t) \to t$
Awarded Nov 30 '21 at 8:45
(post deleted or otherwise unavailable)
Awarded Nov 27 '21 at 22:31
Which universities in the U.S. are doing research in type theory?
Awarded Nov 27 '21 at 20:31
Can this NP-hardness proof for Super Mario Brothers (and other games) be simplified?
Awarded Nov 25 '21 at 8:26
Q: Trusting program output from an untrusted machine
Awarded Nov 23 '21 at 2:06
(post deleted or otherwise unavailable)
Awarded Nov 18 '21 at 22:41
Effect of HoTT/Univalence Axiom on equality between terms of inductive types?
Awarded Nov 14 '21 at 0:36
Hardness of computing the dimension of an integral polytope?
Awarded Nov 12 '21 at 10:56
(post deleted or otherwise unavailable)
Awarded Nov 9 '21 at 23:27
Algorithmic game theory with decentralized mechanism of exchanging information
Awarded Nov 7 '21 at 23:08
Minimize Cumulative Cost on Topological Sort
Awarded Nov 5 '21 at 12:17
A reduction from the maximum $k$-closure problem to the clique problem
Awarded Nov 5 '21 at 10:51
(post deleted or otherwise unavailable)
Awarded Nov 3 '21 at 2:26
(post deleted or otherwise unavailable)
Awarded Oct 30 '21 at 0:38
(post deleted or otherwise unavailable)
Awarded Oct 29 '21 at 1:58
An easy computable injection with a hard inverse
Awarded Oct 28 '21 at 19:50
(post deleted or otherwise unavailable)
Awarded Oct 27 '21 at 21:05
(post deleted or otherwise unavailable)
Awarded Oct 26 '21 at 17:56
(post deleted or otherwise unavailable)
Awarded Oct 21 '21 at 5:05
What is the best text of computation theory/theory of computation?
Awarded Oct 20 '21 at 18:47
Multiplying n polynomials of degree 1
Awarded Oct 20 '21 at 7:56
(post deleted or otherwise unavailable)
Awarded Oct 19 '21 at 19:46
star height of star-free languages
Awarded Oct 18 '21 at 21:06
Does a graph resulting from the union of triangles has a particular name?
Awarded Oct 16 '21 at 5:30
Derandomizing arbitrary width *read-many* and *ordered* branching programs?
Awarded Oct 14 '21 at 15:01
exact path cover for undirected graph
Awarded Oct 14 '21 at 9:06
(post deleted or otherwise unavailable)
Awarded Oct 7 '21 at 11:26
Minimal lexicographical path on DAG in O(||V| + |E|)
Awarded Oct 4 '21 at 12:47
Halting problem for finitary PCF
Awarded Oct 3 '21 at 16:33
(post deleted or otherwise unavailable)
Awarded Oct 3 '21 at 16:16
Are runtime bounds in P decidable? (answer: no)
Awarded Oct 1 '21 at 5:27
(post deleted or otherwise unavailable)
Awarded Sep 30 '21 at 18:36
$\mathbf{AC}^0$ lower bounds for $\mathsf{Gap}\text{-}\mathsf{Max3SAT}$
Awarded Sep 30 '21 at 14:12
Is polynomial-time the same in all classical computational models?
Awarded Sep 28 '21 at 13:55
1
2 3 4 5
…
67

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.