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

Top Questions

12 votes
2 answers
2k views

Algebraic equivalent of SAT?

6 votes
1 answer
148 views

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

4 votes
1 answer
203 views

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

2 votes
1 answer
164 views

Value of studying boolean function complexity through circuits complexity nowadays

3 votes
1 answer
200 views

Relativized world in which P ≠ NP = coNP

18 votes
0 answers
236 views

Can we do integer addition in linear time?

2 votes
1 answer
119 views

Equivalence of a physical computer and Turing machine

2 votes
1 answer
169 views

Fixpoint of a functor in the category of embeddings

2 votes
1 answer
167 views

Chernoff bound for weighted sums of Bernoulli random variables

0 votes
1 answer
112 views

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

0 votes
0 answers
200 views

Claimed proof of PSPACE ⊆ BQP on arXiv

2 votes
1 answer
117 views

Maximum weight matching with surreal weights

0 votes
1 answer
81 views

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

5 votes
0 answers
117 views

Arithmetization of finite automata

-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$

0 votes
1 answer
74 views

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

1 vote
1 answer
72 views

Cover a graph with complete subgraphs

1 vote
0 answers
113 views

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

6 votes
0 answers
81 views

List Functions That Don't Depend on Length

4 votes
0 answers
95 views

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

0 votes
0 answers
86 views

Quantum END OF THE LINE Representation?

3 votes
1 answer
48 views

Free type variables in Hindley-Milner type inference

5 votes
0 answers
61 views

Complexity of the unique homomorphism problem up to automorphisms

-3 votes
0 answers
76 views

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

2 votes
0 answers
71 views

Does GHC use graph reduction?

0 votes
0 answers
70 views

Loseless Data Compression of Bouncing Ball

0 votes
1 answer
49 views

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

1 vote
0 answers
56 views

Is NLOGTIME self-low?

0 votes
0 answers
53 views

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

-1 votes
0 answers
52 views

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

-1 votes
0 answers
51 views

Open complexity theoretic questions for foundation models

2 votes
0 answers
49 views

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

1 vote
1 answer
34 views

Bad Cycles in Interaction Nets

-2 votes
0 answers
38 views

Robacker s-t path Theorem

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)

0 votes
0 answers
37 views

List of calculi suitable for generic computation

4 votes
0 answers
36 views

Error analysis of Estrin's method

1 vote
0 answers
31 views

Building the minimal automaton from the syntactic monoid of a language

-2 votes
0 answers
30 views

Equivalent TRC(Tuple relational calculus) for SQL queries

0 votes
0 answers
30 views

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

-1 votes
0 answers
29 views

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

-2 votes
0 answers
28 views

Extracting one induced subgraph of a given graph

0 votes
0 answers
26 views

Computability for universal quantum turing machines

0 votes
0 answers
23 views

Minimum vertex-separators under edge addition

0 votes
0 answers
21 views

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

0 votes
0 answers
19 views

Proof that Sufficiency and Caliberation by group are equivalent notions

0 votes
1 answer
17 views

Entries of the Inverse Laplacian

0 votes
0 answers
15 views

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


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