Theoretical Computer Science

Teacher

 Teacher
Answer a question with score of 1 or more.
Awarded 2466 times.
Enumerating finite set of words with Hamming distance $1$
Awarded yesterday
Can polynomial sized DNF be used to construct weak PRF
Awarded Jun 28 at 7:56
What is the problem in "closest pair problem" if all points share the same x-coordinate
Awarded Jun 23 at 18:56
Exact Cover by 3-Sets variation: Partition Into Exact Covers by 3-Sets
Awarded Jun 17 at 19:15
What is a "Covering Function"?
Awarded Jun 10 at 19:47
Complexity of optimal elimination for a planar tensor network
Awarded Jun 6 at 11:18
Alternative to binary search trees: A sorted array with empty spaces
Awarded Jun 5 at 9:41
Complexity of the inverse modulo a composite number
Awarded Jun 4 at 2:07
Showing that a modification of an NP-Complete problem is also NP-Complete
Awarded Jun 3 at 22:12
Similarities and differences between Pie and popular languages with dependent types
Awarded May 27 at 19:00
CFG - How can I describe a language that dictates a word and its opposite?
Awarded May 18 at 8:02
Oracle Construction for Grover's Algorithm
Awarded May 17 at 19:40
Growth rate of Knapsack Solutions
Awarded May 15 at 15:36
How to find the size of an ϵ-net of a vector space?
Awarded May 7 at 22:26
Problems Between P and NPC
Awarded May 1 at 13:04
Are trace monoids always syntactic monoids?
Awarded Apr 19 at 16:18
What's the constant coefficient of the Coppersmith-Winograd algorithm?
Awarded Apr 18 at 15:06
Complexity of finding approximate solutions for systems of polynomial equations
Awarded Apr 7 at 17:32
Proving a property of minimal st-separators that are not minimum st-separators
Awarded Apr 6 at 6:25
Find whether a 3CNF formula with every clause having either all the variables negated or all the variables non-negated is satisfiable
Awarded Apr 3 at 1:43
Maximum flow with parity requirement on certain edges
Awarded Mar 26 at 14:55
Directed acyclic graphs with logarithmic diameter
Awarded Mar 24 at 0:37
"Spurious" Type Equivalences in MLSub/Algebraic Subtyping
Awarded Mar 4 at 10:17
Maximum Vertex Cover
Awarded Mar 1 at 14:11
Why does it matter how difficult a proof is?
Awarded Feb 22 at 13:47
Defining functions on non-inductive types using LEM in Coq
Awarded Jan 26 at 5:35
Why can't opaque optics form a category?
Awarded Jan 25 at 0:10
(post deleted or otherwise unavailable)
Awarded Jan 24 at 17:42
(post deleted or otherwise unavailable)
Awarded Jan 21 at 17:08
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, 2021 at 15:27
Deterministic communication complexity of refinement
Awarded Dec 26, 2021 at 16:26
Polynomial-time reducibility of Primality and 3-SAT
Awarded Dec 25, 2021 at 22:32
Is mathematical proof itself NP-hard?
Awarded Dec 25, 2021 at 22:32
Help find algorithm for array-based task
Awarded Dec 25, 2021 at 22:32
Does the Linz Ĥ applied to ⟨Ĥ⟩ correctly transition to its final reject state?
Awarded Dec 25, 2021 at 22:26
Reference request for linear algebra over GF(2)
Awarded Dec 5, 2021 at 4:42
Where does the information in a fractal come from?
Awarded Nov 24, 2021 at 4:51
Q: Trusting program output from an untrusted machine
Awarded Nov 23, 2021 at 6:31
What is "distributed computing" as a field of computer science?
Awarded Nov 22, 2021 at 16:10
Is there a precise definition for big O notation with 2 or more variables
Awarded Nov 21, 2021 at 17:26
(post deleted or otherwise unavailable)
Awarded Nov 15, 2021 at 2:12
Complexity of NFA to DFA minimization with binary threshold
Awarded Nov 8, 2021 at 21:26
Can we approximate the number of words accepted by an NFA?
Awarded Nov 8, 2021 at 3:27
Can this special case of Node Weighted Steiner Tree be solved in polynomial time?
Awarded Nov 6, 2021 at 7:35
Johnson and Lindenstrauss lemma for hamming space
Awarded Nov 4, 2021 at 21:03
What is the general definition of 'extensionality' in type theory and how is extensionality defined for positive types?
Awarded Nov 2, 2021 at 15:32
An easy computable injection with a hard inverse
Awarded Oct 27, 2021 at 0:41
Derandomizing arbitrary width *read-many* and *ordered* branching programs?
Awarded Oct 14, 2021 at 15:25
How does axiom K contradict univalence?
Awarded Sep 25, 2021 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, 2021 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, 2021 at 13:04
Constructing terms of function types out of the empty type
Awarded Aug 29, 2021 at 12:27
Computational Complexity of the Divisor summatory function
Awarded Aug 26, 2021 at 21:56
Short supersequence for many permutations
Awarded Aug 25, 2021 at 21:05
VNP is closed under taking coefficients using Valiant's criterion
Awarded Aug 25, 2021 at 16:30
What are the recent TCS books whose drafts are available online?
Awarded Aug 25, 2021 at 7:05
Complexity of "can we get a cycle by stacking directed bipartite graphs?"
Awarded Aug 24, 2021 at 19:05
Can theoretical computer science be applied in social sciences?
Awarded Aug 18, 2021 at 20:25
Can theoretical computer science be applied in social sciences?
Awarded Aug 17, 2021 at 9:17
1
2 3 4 5
…
42

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.