Top Questions

10 votes
2 answers
625 views

Complexity of NFA cofiniteness

9 votes
1 answer
284 views

Theorem 2.4(i) in Valiant-Vazirani paper "NP is as easy as detecting unique solutions"

8 votes
1 answer
338 views

In logic programming, what would a language with second-order model theory gain?

7 votes
1 answer
309 views

Comparing Shor's and Regev's Quantum Factoring algorithm

3 votes
1 answer
206 views

How to encode a function from an existential type

4 votes
1 answer
124 views

How does gcd in $\mathbb Z_p[x]$ and $\mathbb Z_q[x]$ relate to gcd in $\mathbb Z_n[x]$?

2 votes
1 answer
120 views

Polynomial Identity Testing for $\prod \sum \prod$

0 votes
1 answer
166 views

This is a variant of the unsolved problem of $a^6+b^6+c^6≠d^6+e^6+f^6$, for distinct primes. Does it have any significance for Exact Three Cover?

0 votes
1 answer
92 views

Is there a generalized SAT problem for higher-order logics?

-1 votes
2 answers
135 views

Help understand why FOL wff are enumerable, but FOL is undecidable

3 votes
1 answer
81 views

Testing if a distribution over $\mathbb{F}_2^n$ is heavily supported on a subspace

3 votes
1 answer
103 views

Straight-line program for sets

8 votes
0 answers
131 views

Resources on how to write good TCS papers

1 vote
0 answers
152 views

Relation between $k$-sum failure and $P=NP$

3 votes
1 answer
110 views

How well can shortest common supersequence over small alphabet size be approximated?

4 votes
0 answers
131 views

Learning a regular language with a specified closure property

3 votes
2 answers
72 views

Why is order/choice an issue for a logic for PTIME

0 votes
1 answer
36 views

Can you fix integral LP variables for a non-integral polytope without affecting the existence of integral optima?

5 votes
0 answers
70 views

Hardness of Computing Tribes-DNF by Decision Trees

5 votes
0 answers
88 views

Does there exist a cryptographic associative hash function?

3 votes
0 answers
80 views

Higher dimensional automata?

3 votes
0 answers
79 views

Where is $\mathsf{BPP^{NP}}$ in the polynomial hierarchy?

0 votes
0 answers
78 views

Induced subgraphs with interface

7 votes
0 answers
60 views

Tree of addition chains

0 votes
0 answers
75 views

Proof of coNE ⊆ NE/poly

0 votes
0 answers
74 views

Jukna Boolean Function Complexity Exercises 7.2 & 7.3

1 vote
0 answers
71 views

Separating disjoint PSPACE-hard sets by NP-separators (and some variants)

1 vote
0 answers
65 views

Perceptual similarity problem in theoretical computer science

0 votes
0 answers
65 views

Reductions That Acts on Witnesses

2 votes
0 answers
64 views

On mod $p$ constructions related to determinant

1 vote
0 answers
64 views

Why is the model-checking problem for MSO $\textsf{PSPACE}$-complete?

1 vote
0 answers
62 views

Is there any augmenting graph algorithm available for finding maximum independent set problem in K1,4-free graph in polynomial time

3 votes
0 answers
60 views

Is there a complexity class defined as fixed Boolean combinations of problems in $\mathsf{BPP} \cup \mathsf{BH}$?

1 vote
1 answer
57 views

What are some practical applications of inductive-inductive and inductive-recursive types?

0 votes
0 answers
56 views

Complexity of LSB and MSB of Diffie-Hellman

-3 votes
0 answers
56 views

Is there a generalized SAT problem for many-valued logics?

0 votes
0 answers
54 views

Why can't we just reduce from Bounded HALT to Bounded PCP?

-1 votes
0 answers
54 views

NTM preserving modular number of accepting paths

0 votes
0 answers
53 views

Has multiobjective prize collecting steiner tree or TSP been studied?

-2 votes
0 answers
52 views

Graph theoretic problems complete for certain counting classes

2 votes
0 answers
52 views

Im looking for papers to read to strengthen my understanding of overall cs theory

3 votes
0 answers
50 views

Partial Hamiltonian Path Optimization Problem

3 votes
0 answers
48 views

Hardness of deciding fractional chromatic number at most $k$

2 votes
0 answers
47 views

Do prefix hash functions work well for approximate counting?

0 votes
0 answers
46 views

cutting plane method for convex optimization

0 votes
0 answers
43 views

For which k can we decide whether an input k-gon tiles?

0 votes
0 answers
42 views

On a modular inverse graph construction

0 votes
0 answers
42 views

Is checking at least $k$ solutions as hard as counting?


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