Theoretical Computer Science

Teacher

 Teacher
Answer a question with score of 1 or more.
Awarded 2387 times.
Does replacing each vertex of $G$ by $H$ increase treewidth of $G$ by at most $\Delta(G)$?
Awarded Apr 15 at 6:53
The concept of binary description by Ray Solomonoff
Awarded Apr 13 at 7:25
Why does Coq have Prop?
Awarded Apr 9 at 10:49
kmeans++ for arbitrary metric spaces and general potential function
Awarded Apr 6 at 19:08
What papers should everyone read?
Awarded Apr 6 at 8:30
Algorithm to find $n$ player nash equilibrium
Awarded Apr 4 at 17:25
Weak incidence colouring
Awarded Apr 4 at 12:10
Graph labelling where vertices with a common neighbour get different labels
Awarded Mar 22 at 6:18
What is the best text of computation theory/theory of computation?
Awarded Mar 21 at 19:45
Defining inductive types in intensional type theory purely in terms of type-theoretic data
Awarded Mar 17 at 9:49
Surjection from a type to a universe
Awarded Mar 14 at 12:08
Can modern SAT-Solvers utilise the symmetry of First Order Logic?
Awarded Mar 11 at 8:25
Is this variant of bitwise cyclic tag Turing-complete?
Awarded Mar 5 at 21:31
A possible error in the semantic chapter of the ISO standard for the Z specification notation
Awarded Mar 5 at 4:11
What advantages does having a null-able string type confer to a programming language?
Awarded Mar 4 at 10:56
Is the exponent in the rectangular matrix multiplication convex?
Awarded Feb 27 at 14:56
Is the exponent in the rectangular matrix multiplication convex?
Awarded Feb 25 at 13:43
Does Memcomputing really solve an NP-complete problem?
Awarded Feb 24 at 17:42
Have these coloring games been solved?
Awarded Feb 24 at 1:27
An invariance theorem for algorithmically random data in statistical learning
Awarded Feb 22 at 10:36
What would be the performance properties of a comb or shell sort where the gap sequence is the prime numbers?
Awarded Feb 19 at 9:26
Is there a fast algorithm to quickly evaluate $a^{b^c}$ mod $n$?
Awarded Feb 16 at 18:41
NP-Completeness of Finding Minimum Automaton, in Gold's paper
Awarded Feb 14 at 18:56
How to solve an unification problem on $\mathbb{N}$?
Awarded Feb 12 at 15:55
Average-case randomized communication complexity in the small-advantage regime
Awarded Feb 10 at 19:52
VC generalization bound extended to other types of target functions
Awarded Feb 5 at 4:50
Finite-State Automata over a real-valued alphabet
Awarded Feb 4 at 15:31
NP-hardness of a planar SAT variant
Awarded Feb 1 at 2:25
Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient
Awarded Jan 28 at 13:17
Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient
Awarded Jan 28 at 12:51
Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient
Awarded Jan 28 at 12:43
Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient
Awarded Jan 28 at 11:18
Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient
Awarded Jan 27 at 17:57
Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient
Awarded Jan 27 at 15:51
Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient
Awarded Jan 27 at 15:12
Variable wire weights in DLOGTIME-uniform circuits
Awarded Jan 23 at 0:10
Reducing #SAT to MAJ-SAT
Awarded Jan 22 at 17:04
Lipschitz composable compressor
Awarded Jan 22 at 16:04
An axiom for John Major's Equality
Awarded Jan 18 at 17:06
CNF encoding of set cover - NExpTime-completness
Awarded Jan 17 at 12:46
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
1
2 3 4 5
…
40

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.