Theoretical Computer Science

Scholar

 Scholar
Ask a question and accept an answer.
Awarded 2354 times.
Can the halting problem be solved probabilistically?
Awarded 27 mins ago
VC dimension for balanced binary decision trees
Awarded Oct 17 at 8:26
Time complexity of finding chain decomposition of partially ordered set
Awarded Oct 17 at 1:02
On the usage of Arora and Barak's main lemma in their proof of the PCP theorem
Awarded Oct 16 at 15:31
Which are the best universities for a DPhil/PhD in proof theory and automated reasoning?
Awarded Oct 15 at 23:11
Number of maximal cliques in a ($2C_4$, $C_5$, $P_5$)-free graph
Awarded Oct 9 at 20:31
Complexity of type inference in the simply typed lambda calculus
Awarded Oct 8 at 15:20
Series-parallel DAG characterization
Awarded Oct 2 at 13:55
Sum-of-Squares Certificates
Awarded Sep 29 at 22:47
Rademacher Complexity of the Composition with an Indicator
Awarded Sep 27 at 1:57
Dependence of decidability on the encoding of Turing machines
Awarded Sep 21 at 8:25
Can you find a counter-example for this proposed Graph Isomorphism algorithm?
Awarded Sep 19 at 12:10
Isomorphism of ‘ordered’ DAGs / acyclic semiautomata
Awarded Sep 12 at 23:17
Generate cut $(A,B)$ in edge-colored graph $(V,E_1 \cup E_2)$ such that there are more red than white crossings, i.e $|E_1(A,B)| > |E_2(A,B)|$
Awarded Sep 9 at 17:49
Pi-calculus (or session types) - proof for weakening lemma
Awarded Sep 8 at 10:02
Graphs-like data structure with weighted vertices
Awarded Sep 7 at 17:36
Explicit Bits-back Coding (a.k.a. Free Energy Coding) applied to Gaussian mixtures
Awarded Sep 6 at 3:28
Isomorphic graph embeddings in the Euclidean Space
Awarded Aug 20 at 14:20
Maximum subarray problem with weights
Awarded Aug 17 at 21:37
Complexity of acyclicity of a “nondeterministic” graph
Awarded Aug 15 at 9:48
Formal theory about explaining algorithms
Awarded Aug 12 at 11:05
How can I find the PhD thesis of C.A. Ellis?
Awarded Aug 11 at 8:25
Rewrite relations - proof of correctness
Awarded Aug 9 at 8:12
An efficient Beta-Equivalence algorithm?
Awarded Aug 4 at 2:04
approximate maximum clique given vertex cover
Awarded Jul 21 at 17:57
Zero Knowledge proofs of knowledge
Awarded Jul 21 at 11:33
Understanding definition of #P
Awarded Jul 20 at 19:51
Is there a language of first-order logic such that every r.e. set is Turing-equivalent to some finitely axiomatizable theory in that language?
Awarded Jul 15 at 21:35
Is mathematical proof itself NP-hard?
Awarded Jul 15 at 17:16
Neighborly properties in a bipartite graph
Awarded Jul 13 at 22:35
Is there an official/academic name for the “current value” in a loop? [closed]
Awarded Jul 7 at 5:11
Length bounded minimum cardinality cut in DAGs
Awarded Jul 3 at 6:40
Complexity relative to the graph of the Busy-Beaver function
Awarded Jul 1 at 22:17
Beta reduction and vacuous lambda abstraction [closed]
Awarded Jul 1 at 10:19
Why do people bring real-life Quantum Computing to the discussion of the Church-Turing thesis?
Awarded Jun 29 at 16:17
Why would the term “dynamically typed” be considered a misnomer?
Awarded Jun 27 at 14:09
What kind of computational model is the brain? [duplicate]
Awarded Jun 27 at 4:11
Deciding whether a 2nfa halts on every input on every branch
Awarded Jun 20 at 23:08
Google quantum supremacy experiment data
Awarded Jun 17 at 16:34
Number of connected components of a random nearest neighbor graph?
Awarded Jun 13 at 10:35
Tree decompositions of optimal width where every vertex is in a bounded number of bags?
Awarded Jun 4 at 21:25
Choosing one number from each set so that the sum of squares of each distinct number counts is minimized
Awarded Jun 3 at 4:55
Adjective for: algorithm that outputs its input if it is one of its outputs?
Awarded Jun 2 at 8:21
how to achieve a topological sort of an given sequence with minimum swaps
Awarded Jun 1 at 11:30
What arithmetical theorems can plain $\lambda \Pi$ reason about?
Awarded May 28 at 15:40
Additive versus multiplicative accuracy
Awarded May 23 at 18:32
Can a result of (any) hash algorithm contain the hash result itself?
Awarded May 22 at 23:11
Intuition behind the Charikar's LP formulation for densest subgraph problem
Awarded May 20 at 23:09
Is $\{0,1\}$-Vector bin packing NP-Hard when vectors have constant dimension?
Awarded May 20 at 8:18
How do conference proceedings add to academic prestige?
Awarded May 19 at 14:47
How to prove that Supremum preorder coincides with Hoare preorder?
Awarded May 18 at 19:11
Degree restriction for polynomials in $\mathsf{VP}$
Awarded May 17 at 11:04
Are there any public synchronous discussion forums (slack, discord, etc.) for TCS
Awarded May 15 at 15:40
A boolean function $f: \{0,1\}^n \rightarrow \{0,1\}$ is chosen at random from all $2^{2^n}$ such $f$. What do the Fourier coefficients look like?
Awarded May 13 at 17:32
On the complexity of a “list” datastructure in the RAM model
Awarded May 5 at 16:35
Why Asymptotic Equipartition Property theorem proofs assume the source is memoryless?
Awarded May 5 at 2:50
Is there an assumption that implies $P=ZPP$ which is not known to imply $P=BPP$?
Awarded May 4 at 3:07
Minimum non-zero variable in the optimal solution of linear programming
Awarded Apr 30 at 15:38
What are some standard books/papers on Information Theory?
Awarded Apr 27 at 19:47
Is there any equation-based method for transforming Büchi-automata to omega-regular language?
Awarded Apr 26 at 15:45
1
2 3 4 5
…
40