Theoretical Computer Science

Teacher

 Teacher
Answer a question with score of 1 or more.
Awarded 2314 times.
Examples of collapsing hierarchies
Awarded Aug 5 at 12:31
Examples of collapsing hierarchies
Awarded Aug 5 at 12:05
Why do people bring real-life Quantum Computing to the discussion of the Church-Turing thesis?
Awarded Jul 26 at 23:49
approximate maximum clique given vertex cover
Awarded Jul 21 at 19:40
Fully dynamic algorithms for strong components of a directed graph
Awarded Jul 20 at 6:34
Complexity of Set Difference
Awarded Jul 17 at 17:47
3SUM Complexity—A special(?) Case
Awarded Jul 12 at 1:41
Good Survey paper for k-means/k-median/k-center/facility-location
Awarded Jul 9 at 9:51
What evidences are there that $PP$ is in $BQP$ and $PP$ is not in $BQP$?
Awarded Jul 9 at 4:25
Can modern SAT-Solvers utilise the symmetry of First Order Logic?
Awarded Jul 7 at 21:19
Continued Fraction Algorithm in Shor's Algorithm
Awarded Jul 7 at 9:15
Is there an official/academic name for the “current value” in a loop?
Awarded Jul 7 at 5:11
Counting words of length $n$ in an inherently ambiguous CFG?
Awarded Jul 5 at 20:48
Minimum distance of a code
Awarded Jun 27 at 1:57
Efficient algorithm to find overlapping circles of various sizes
Awarded Jun 26 at 19:52
Any fundamental papers in TCS which were found to be incorrect/wrong later?
Awarded Jun 23 at 10:12
Are all RegExp solvable in O(n)?
Awarded Jun 18 at 23:35
Direct SAT to 3-SAT reduction
Awarded Jun 14 at 22:49
Tree decompositions of optimal width where every vertex is in a bounded number of bags?
Awarded Jun 4 at 22:48
Any fundamental papers in TCS which were found to be incorrect/wrong later?
Awarded May 30 at 20:50
Disjoint subsets problem complexity
Awarded May 26 at 2:04
Maximizing difference of a submodular and a modular function
Awarded May 20 at 14:50
Are there any public synchronous discussion forums (slack, discord, etc.) for TCS
Awarded May 15 at 17:02
What would a very simple quantum program look like?
Awarded May 15 at 15:25
Why non-uniform learnability does not imply PAC learnability?
Awarded May 14 at 16:43
Uses of algebraic structures in theoretical computer science
Awarded May 12 at 4:48
Definition of Omega Jump
Awarded May 9 at 18:45
Why Asymptotic Equipartition Property theorem proofs assume the source is memoryless?
Awarded May 3 at 0:07
(post deleted or otherwise unavailable)
Awarded May 2 at 16:50
Constraints on sliding windows
Awarded Apr 29 at 21:40
(post deleted or otherwise unavailable)
Awarded Apr 29 at 19:19
Busy Beaver Equivalent for the Untyped Lambda Calculus
Awarded Apr 24 at 5:08
Interval partitioning with restrictions: NP-complete or efficiently solvable?
Awarded Apr 19 at 14:28
Formally Verified Complexity Theory
Awarded Apr 18 at 18:12
Password checking algorithm
Awarded Apr 18 at 13:26
Reference Request: Computational Learning Theory
Awarded Apr 17 at 21:12
Reference Request: Computational Learning Theory
Awarded Apr 17 at 18:57
Multimodal logic with quantification over modal operators
Awarded Apr 15 at 10:20
Is there any connection between the diamond norm and the distance of the associated states?
Awarded Apr 14 at 7:20
What is the minimal class of subshifts for which conjugacy is known to be undecidable?
Awarded Apr 11 at 17:50
Time complexity for multiplying two lower triangular matrices
Awarded Apr 8 at 4:45
What Books Should Everyone Read?
Awarded Apr 5 at 6:15
What podcast should everybody listen to?
Awarded Apr 5 at 1:35
Best Upper Bounds on SAT
Awarded Mar 20 at 10:10
Is it possible to sort by only knowing the sign of pairwise sums?
Awarded Mar 12 at 22:40
Has the compactness theorem for FOL been formalized in Coq/Isabelle/etc?
Awarded Mar 10 at 2:20
Is there a notion of indistinguishability obfuscation for almost equivalent circuits?
Awarded Mar 9 at 8:25
FO(TC) lower bounding games?
Awarded Mar 5 at 15:45
Results on universal approximation for learners other than ANNs
Awarded Feb 27 at 15:45
What would be the next step after quantum computing?
Awarded Feb 27 at 15:20
What tools do you use to give presentations?
Awarded Feb 21 at 15:55
How is proving a context free language to be ambiguous undecidable?
Awarded Feb 18 at 8:50
Major unsolved problems in theoretical computer science?
Awarded Feb 10 at 17:25
Infinite process balls in bins problem
Awarded Feb 10 at 9:20
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 Feb 5 at 5:50
Lack of atomic propositions in the Calculus of Constructions from ATTAPL textbook
Awarded Feb 4 at 20:00
Minimum Unsatisfiable 3-CNF Formulae
Awarded Feb 2 at 5:40
Type of induction principle for fixpoint types
Awarded Feb 1 at 2:15
W[1]-hard problems with FPT time approximation algorithms
Awarded Jan 29 at 18:25
Minimum Unsatisfiable 3-CNF Formulae
Awarded Jan 24 at 7:00
1
2 3 4 5
…
39