Theoretical Computer Science

Teacher

 Teacher
Answer a question with score of 1 or more.
Awarded 2408 times.
An (unusual?) risk bound
Awarded Jul 31 at 1:18
(post deleted or otherwise unavailable)
Awarded Jul 28 at 1:51
Treewidth of monotone graph classes with bounded cliquewidth
Awarded Jul 26 at 0:15
Why is finding the ground state of a Hamiltonian in QMA?
Awarded Jul 21 at 7:40
(post deleted or otherwise unavailable)
Awarded Jul 14 at 6:41
Reviewing a paper and found a better solution
Awarded Jul 13 at 8:51
Ajtai's Proof of Theorem 1 in 'Generating Hard Instances of Lattice Problems'
Awarded Jun 25 at 21:42
Separating words with random DFAs
Awarded Jun 24 at 6:32
Knapsack problem with dependent weight and profits among the items
Awarded Jun 21 at 0:33
Examples of the price of abstraction?
Awarded Jun 16 at 19:02
Why do TCS papers have author names in alphabetical order of their surnames?
Awarded May 31 at 7:52
The complexity of determining if a fixed graph is a minor of another
Awarded May 31 at 6:55
Maximum cliques of the transitive closure of a chordal DAG
Awarded May 20 at 9:17
Explaining monad transformers in categorical terms
Awarded May 19 at 7:11
NP-complete decision problems on deterministic automata
Awarded May 16 at 11:04
Are there strongly normalizing lambda terms that cannot be given a System F type?
Awarded May 1 at 11:49
Covering a binary relation as a union of rectangles
Awarded Apr 30 at 5:55
Proving not NP-complete by non-existence of gadget
Awarded Apr 28 at 10:48
Hardness when restricted to an infinite number of far apart instance sizes
Awarded Apr 28 at 3:46
Algorithms Careers
Awarded Apr 27 at 2:56
Algorithms Careers
Awarded Apr 24 at 4:34
What are some problems where we know we have an optimal algorithm?
Awarded Apr 23 at 15:36
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
(post deleted or otherwise unavailable)
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
1
2 3 4 5
…
41

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.