Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.

Sign up to join this community
Anybody can ask a question
Anybody can answer
The best answers are voted up and rise to the top
Theoretical Computer Science

Top Questions

Ask Question
Active Hot Week Month
12 votes
2 answers
2k views

Algebraic equivalent of SAT?

D.W.
  • 11.1k
6 votes
1 answer
148 views

Is it $NP$-hard to check whether a given algebraic circuit computes permanent?

questionmaster
  • 61
4 votes
1 answer
203 views

Relationship between the transition monoid of an automaton and its adjacency matrix

Shaull
  • 5,501
2 votes
1 answer
164 views

Value of studying boolean function complexity through circuits complexity nowadays

Emil Jeřábek
  • 15.3k
3 votes
1 answer
200 views

Relativized world in which P ≠ NP = coNP

Emil Jeřábek
  • 15.3k
18 votes
0 answers
236 views

Can we do integer addition in linear time?

Emil Jeřábek
  • 15.3k
2 votes
1 answer
119 views

Equivalence of a physical computer and Turing machine

Jim Hefferon
  • 213
2 votes
1 answer
169 views

Fixpoint of a functor in the category of embeddings

LaR
  • 163
2 votes
1 answer
167 views

Chernoff bound for weighted sums of Bernoulli random variables

Neal Young
  • 9,243
0 votes
1 answer
112 views

What is the simplest one-way function (in terms of boolean circuit complexity)?

D.W.
  • 11.1k
0 votes
0 answers
200 views

Claimed proof of PSPACE ⊆ BQP on arXiv

kodlu
  • 2,039
2 votes
1 answer
117 views

Maximum weight matching with surreal weights

Emil Jeřábek
  • 15.3k
0 votes
1 answer
81 views

Boosting the probability of success(random projections, johnson lindenstrauss)

Sid Jain
  • 31
5 votes
0 answers
117 views

Arithmetization of finite automata

user1868607
  • 889
-3 votes
0 answers
133 views

The generated proof $h_{1}k_{1}k_{2}^{-1}h_{2}^{-1}\in\left\{h\cdot k\mid h\in H,k\in K\right\}$ for $\cdots j^{-1}i^{-1}h^{-1}g^{-1}kghij\cdots\in K$

Robbinspire
  • 53
0 votes
1 answer
74 views

Nonconstructive $\log(n)$ seed length PRG for fooling modular tests

Jason Gaitonde
  • 775
1 vote
1 answer
72 views

Cover a graph with complete subgraphs

Neal Young
  • 9,243
1 vote
0 answers
113 views

What advancements in SMT solvers have contributed to progress in the field of theoretical computer science?

hddmss
  • 71
6 votes
0 answers
81 views

List Functions That Don't Depend on Length

vigenary
  • 61
4 votes
0 answers
95 views

$\mathsf{NL}$ vs. $\mathsf{AC}^1$

Alexey Milovanov
  • 1,787
0 votes
0 answers
86 views

Quantum END OF THE LINE Representation?

wavosa
  • 3
3 votes
1 answer
48 views

Free type variables in Hindley-Milner type inference

Brian Berns
  • 151
5 votes
0 answers
61 views

Complexity of the unique homomorphism problem up to automorphisms

Rémi
  • 51
-3 votes
0 answers
76 views

Relation between $NC^i$ and $L^i$

Turbo
  • 12.6k
2 votes
0 answers
71 views

Does GHC use graph reduction?

geeko
  • 131
0 votes
0 answers
70 views

Loseless Data Compression of Bouncing Ball

Todd Takala
  • 101
0 votes
1 answer
49 views

Number of equivalent formulas in a function-free first order logic language?

Reijo Jaakkola
  • 870
1 vote
0 answers
56 views

Is NLOGTIME self-low?

l4m2
  • 111
0 votes
0 answers
53 views

How can we establish that Gödel's completeness theorem corresponds to an interactive disassembler?

Aramya
  • 1
-1 votes
0 answers
52 views

Kxy in SKI combinator calculus: why include y if K always ignores it?

Hank Igoe
  • 99
-1 votes
0 answers
51 views

Open complexity theoretic questions for foundation models

Omar Shehab
  • 713
2 votes
0 answers
49 views

hardness of partition of permutation into a minimum number of monotone subsequences

steven kelk
  • 71
1 vote
1 answer
34 views

Bad Cycles in Interaction Nets

D.W.
  • 11.1k
-2 votes
0 answers
38 views

Robacker s-t path Theorem

Amir.S
  • 97
2 votes
0 answers
38 views

Is there a name and context where function for permutation defined as f(k) = #σ({1,2,…,k})∩{1,2,…,k} appeared ? (Measure of locality)

Alexander Chervov
  • 263
0 votes
0 answers
37 views

List of calculi suitable for generic computation

geeko
  • 131
4 votes
0 answers
36 views

Error analysis of Estrin's method

Thomas Ahle
  • 838
1 vote
0 answers
31 views

Building the minimal automaton from the syntactic monoid of a language

gigabytes
  • 1,366
-2 votes
0 answers
30 views

Equivalent TRC(Tuple relational calculus) for SQL queries

Khoka420
  • 1
0 votes
0 answers
30 views

What does doing a tensor network contraction "for bond dimension k" mean?

spreinhardt
  • 1
-1 votes
0 answers
29 views

Characterizing indices of p.c. functions when intersected over arity

trillianhaze
  • 19
-2 votes
0 answers
28 views

Extracting one induced subgraph of a given graph

mahou_2019
  • 9
0 votes
0 answers
26 views

Computability for universal quantum turing machines

Shane Gervais
  • 1
0 votes
0 answers
23 views

Minimum vertex-separators under edge addition

BBK
  • 85
0 votes
0 answers
21 views

Complexity of feasibility of a system of linear and restricted non-linear inequalities

user1868607
  • 889
0 votes
0 answers
19 views

Proof that Sufficiency and Caliberation by group are equivalent notions

Segun Ojo
  • 1
0 votes
1 answer
17 views

Entries of the Inverse Laplacian

Zuza
  • 131
0 votes
0 answers
15 views

How to estimate the order of magnitude of the solution to a closest vector problem?

haoyu
  • 1

Looking for more? Browse the complete list of questions, or popular tags. Help us answer unanswered questions.

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.