Theoretical Computer Science

Teacher

 Teacher
Answer a question with score of 1 or more.
Awarded 2439 times.
Is there an efficient construction for a trilinear pairing that has been used in theory or practice
Awarded Jan 10 at 6:36
Why is "topological sorting" topological?
Awarded Dec 27 '21 at 15:27
Deterministic communication complexity of refinement
Awarded Dec 26 '21 at 16:26
Polynomial-time reducibility of Primality and 3-SAT
Awarded Dec 25 '21 at 22:32
Is mathematical proof itself NP-hard?
Awarded Dec 25 '21 at 22:32
Help find algorithm for array-based task
Awarded Dec 25 '21 at 22:32
What final state does simplified Linz Ĥ applied to ⟨Ĥ⟩ transition to?
Awarded Dec 25 '21 at 22:26
Reference request for linear algebra over GF(2)
Awarded Dec 5 '21 at 4:42
Where does the information in a fractal come from?
Awarded Nov 24 '21 at 4:51
Q: Trusting program output from an untrusted machine
Awarded Nov 23 '21 at 6:31
What is "distributed computing" as a field of computer science?
Awarded Nov 22 '21 at 16:10
Is there a precise definition for big O notation with 2 or more variables
Awarded Nov 21 '21 at 17:26
(post deleted or otherwise unavailable)
Awarded Nov 15 '21 at 2:12
Complexity of NFA to DFA minimization with binary threshold
Awarded Nov 8 '21 at 21:26
Can we approximate the number of words accepted by an NFA?
Awarded Nov 8 '21 at 3:27
Can this special case of Node Weighted Steiner Tree be solved in polynomial time?
Awarded Nov 6 '21 at 7:35
Johnson and Lindenstrauss lemma for hamming space
Awarded Nov 4 '21 at 21:03
What is the general definition of 'extensionality' in type theory and how is extensionality defined for positive types?
Awarded Nov 2 '21 at 15:32
An easy computable injection with a hard inverse
Awarded Oct 27 '21 at 0:41
Derandomizing arbitrary width *read-many* and *ordered* branching programs?
Awarded Oct 14 '21 at 15:25
How does axiom K contradict univalence?
Awarded Sep 25 '21 at 10:19
How do we evalute the difference between a predicted value $\hat{v}$ and the true nash equlibrium value $v$
Awarded Sep 20 '21 at 18:11
Is Barbara Liskov's claim that CLU was the first implemented language to provide linguistic support for data abstraction accurate?
Awarded Sep 18 '21 at 13:04
Constructing terms of function types out of the empty type
Awarded Aug 29 '21 at 12:27
Computational Complexity of the Divisor summatory function
Awarded Aug 26 '21 at 21:56
Short supersequence for many permutations
Awarded Aug 25 '21 at 21:05
VNP is closed under taking coefficients using Valiant's criterion
Awarded Aug 25 '21 at 16:30
What are the recent TCS books whose drafts are available online?
Awarded Aug 25 '21 at 7:05
Complexity of "can we get a cycle by stacking directed bipartite graphs?"
Awarded Aug 24 '21 at 19:05
Can theoretical computer science be applied in social sciences?
Awarded Aug 18 '21 at 20:25
Can theoretical computer science be applied in social sciences?
Awarded Aug 17 '21 at 9:17
Can theoretical computer science be applied in social sciences?
Awarded Aug 16 '21 at 19:57
Lexicographic Boolean satisfiability
Awarded Aug 13 '21 at 19:31
Given two languages and their grammars can you translate from one to the other?
Awarded Aug 5 '21 at 15:18
An (unusual?) risk bound
Awarded Jul 31 '21 at 1:18
(post deleted or otherwise unavailable)
Awarded Jul 28 '21 at 1:51
Treewidth of monotone graph classes with bounded cliquewidth
Awarded Jul 26 '21 at 0:15
Why is finding the ground state of a Hamiltonian in QMA?
Awarded Jul 21 '21 at 7:40
(post deleted or otherwise unavailable)
Awarded Jul 14 '21 at 6:41
Reviewing a paper and found a better solution
Awarded Jul 13 '21 at 8:51
Ajtai's Proof of Theorem 1 in 'Generating Hard Instances of Lattice Problems'
Awarded Jun 25 '21 at 21:42
Separating words with random DFAs
Awarded Jun 24 '21 at 6:32
Knapsack problem with dependent weight and profits among the items
Awarded Jun 21 '21 at 0:33
Examples of the price of abstraction?
Awarded Jun 16 '21 at 19:02
Why do TCS papers have author names in alphabetical order of their surnames?
Awarded May 31 '21 at 7:52
The complexity of determining if a fixed graph is a minor of another
Awarded May 31 '21 at 6:55
Maximum cliques of the transitive closure of a chordal DAG
Awarded May 20 '21 at 9:17
Explaining monad transformers in categorical terms
Awarded May 19 '21 at 7:11
NP-complete decision problems on deterministic automata
Awarded May 16 '21 at 11:04
Are there strongly normalizing lambda terms that cannot be given a System F type?
Awarded May 1 '21 at 11:49
Covering a binary relation as a union of rectangles
Awarded Apr 30 '21 at 5:55
Proving not NP-complete by non-existence of gadget
Awarded Apr 28 '21 at 10:48
Hardness when restricted to an infinite number of far apart instance sizes
Awarded Apr 28 '21 at 3:46
Algorithms Careers
Awarded Apr 27 '21 at 2:56
Algorithms Careers
Awarded Apr 24 '21 at 4:34
What are some problems where we know we have an optimal algorithm?
Awarded Apr 23 '21 at 15:36
Does replacing each vertex of $G$ by $H$ increase treewidth of $G$ by at most $\Delta(G)$?
Awarded Apr 15 '21 at 6:53
The concept of binary description by Ray Solomonoff
Awarded Apr 13 '21 at 7:25
Why does Coq have Prop?
Awarded Apr 9 '21 at 10:49
kmeans++ for arbitrary metric spaces and general potential function
Awarded Apr 6 '21 at 19:08
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.