Theoretical Computer Science

Teacher

 Teacher
Answer a question with score of 1 or more.
Awarded 2350 times.
An axiom for John Major's Equality
Awarded 7 hours ago
CNF encoding of set cover - NExpTime-completness
Awarded yesterday
Importance of irrational numbers in computer science
Awarded Jan 13 at 18:22
Formalization of simulation for Turing machines
Awarded Jan 10 at 23:06
Knowing if there are two solutions to the subset sum problem
Awarded Jan 8 at 17:03
Check if graph stays connected after edge swap
Awarded Jan 5 at 13:41
Nonterminal descriptional complexity of regular languages
Awarded Jan 3 at 3:06
Analogue of $k$-wise independence for other distributions than uniform
Awarded Jan 2 at 21:45
Survey on Quantum error correction
Awarded Jan 1 at 3:26
One-way randomized communication complexity of Greater-Than
Awarded Dec 30 '20 at 17:57
(post deleted or otherwise unavailable)
Awarded Dec 29 '20 at 10:17
What math courses should I revisit to prepare for a CS Ph.D. (Reinforcement learning and Game Theory)?
Awarded Dec 22 '20 at 5:27
Minimizing $L_2$ norm of a vector with two distinct entries
Awarded Dec 18 '20 at 11:48
An extension to the student/college admissions Gale-Shapley algorithm
Awarded Dec 17 '20 at 6:05
Can concurrency models be compared in terms of some metrics?
Awarded Dec 16 '20 at 17:01
Implementation of alpha equivalence
Awarded Dec 16 '20 at 8:30
Can factorial be encoded in the Kappa-calculus with fixed point operator?
Awarded Dec 16 '20 at 8:30
Converting a Bernoulli to a Gaussian
Awarded Dec 16 '20 at 0:51
Generating a pseudo random Rubik's cube in $O(n^{2+\epsilon})$ time
Awarded Dec 10 '20 at 19:51
Is there any connection between the diamond norm and the distance of the associated states?
Awarded Nov 26 '20 at 15:36
Finding outer face in plane graph (embedded planar graph)
Awarded Nov 20 '20 at 21:05
Complexity of Finding the Eigendecomposition of a Matrix
Awarded Nov 18 '20 at 14:42
Bounds on this Strategy for Separating Words
Awarded Nov 13 '20 at 22:04
Complete axiomatization of relation algebras without ${}^-$ and $\top$
Awarded Nov 10 '20 at 10:48
(post deleted or otherwise unavailable)
Awarded Oct 26 '20 at 9:40
How to calculate complexity in a high dimensional space?
Awarded Oct 22 '20 at 17:06
Bounds on this Strategy for Separating Words
Awarded Oct 15 '20 at 0:01
Are there protein-based computational models?
Awarded Oct 7 '20 at 1:32
Publishing by showing falsity of existing results
Awarded Sep 23 '20 at 7:50
Realizability theory: difference in power between Lambda calculus and Turing Machines
Awarded Sep 23 '20 at 1:16
(post deleted or otherwise unavailable)
Awarded Sep 22 '20 at 3:40
Big O question concerning time complexity
Awarded Sep 14 '20 at 7:36
Pi-calculus (or session types) - proof for weakening lemma
Awarded Sep 8 '20 at 14:11
Explicit Bits-back Coding (a.k.a. Free Energy Coding) applied to Gaussian mixtures
Awarded Sep 5 '20 at 4:08
Reference request: Arithmetic circuit complexity
Awarded Sep 1 '20 at 18:33
Uncountability in intuitionistic logic
Awarded Aug 26 '20 at 13:30
What are some algorithms where space complexity tends to be the limiting factor in practice?
Awarded Aug 21 '20 at 4:42
What are some algorithms where space complexity tends to be the limiting factor in practice?
Awarded Aug 19 '20 at 16:32
What are some algorithms where space complexity tends to be the limiting factor in practice?
Awarded Aug 16 '20 at 20:47
Examples of collapsing hierarchies
Awarded Aug 5 '20 at 12:31
Examples of collapsing hierarchies
Awarded Aug 5 '20 at 12:05
Why do people bring real-life Quantum Computing to the discussion of the Church-Turing thesis?
Awarded Jul 26 '20 at 23:49
approximate maximum clique given vertex cover
Awarded Jul 21 '20 at 19:40
Fully dynamic algorithms for strong components of a directed graph
Awarded Jul 20 '20 at 6:34
Complexity of Set Difference
Awarded Jul 17 '20 at 17:47
3SUM Complexity—A special(?) Case
Awarded Jul 12 '20 at 1:41
Good Survey paper for k-means/k-median/k-center/facility-location
Awarded Jul 9 '20 at 9:51
What evidences are there that $PP$ is in $BQP$ and $PP$ is not in $BQP$?
Awarded Jul 9 '20 at 4:25
Can modern SAT-Solvers utilise the symmetry of First Order Logic?
Awarded Jul 7 '20 at 21:19
Continued Fraction Algorithm in Shor's Algorithm
Awarded Jul 7 '20 at 9:15
Is there an official/academic name for the “current value” in a loop?
Awarded Jul 7 '20 at 5:11
Counting words of length $n$ in an inherently ambiguous CFG?
Awarded Jul 5 '20 at 20:48
Minimum distance of a code
Awarded Jun 27 '20 at 1:57
Efficient algorithm to find overlapping circles of various sizes
Awarded Jun 26 '20 at 19:52
Any fundamental papers in TCS which were found to be incorrect/wrong later?
Awarded Jun 23 '20 at 10:12
Are all RegExp solvable in O(n)?
Awarded Jun 18 '20 at 23:35
Direct SAT to 3-SAT reduction
Awarded Jun 14 '20 at 22:49
Tree decompositions of optimal width where every vertex is in a bounded number of bags?
Awarded Jun 4 '20 at 22:48
Any fundamental papers in TCS which were found to be incorrect/wrong later?
Awarded May 30 '20 at 20:50
Disjoint subsets problem complexity
Awarded May 26 '20 at 2:04
1
2 3 4 5
…
40