Top Questions

1 vote
0 answers
19 views

Higher dimensional automata?

1 vote
0 answers
19 views

Do prefix hash functions work well for approximate counting?

0 votes
0 answers
47 views

Proof of coNE ⊆ NE/poly

3 votes
0 answers
51 views

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

3 votes
1 answer
51 views

Straight-line program for sets

4 votes
0 answers
122 views

Question about Valiant-Vazirani paper "NP is as easy as detecting unique solutions"

0 votes
0 answers
33 views

Induced subgraphs with interface

1 vote
0 answers
24 views

Is the Maximum Coverage Problem Remains as Hard when Taking Most Sets?

2 votes
0 answers
27 views

Generalization of the generalization of the evasiveness conjecture

0 votes
1 answer
156 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?

-1 votes
0 answers
16 views

Neighborhood in a graph coloring problem

4 votes
1 answer
114 views

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

8 votes
0 answers
117 views

Resources on how to write good TCS papers

0 votes
0 answers
40 views

On a modular inverse graph construction

0 votes
1 answer
72 views

Hardnnes of Approximation of Minimum Vertex Cover on 3-Regular Graphs

0 votes
0 answers
71 views

Jukna Boolean Function Complexity Exercises 7.2 & 7.3

2 votes
0 answers
59 views

On mod $p$ constructions related to determinant

3 votes
0 answers
46 views

Partial Hamiltonian Path Optimization Problem

11 votes
11 answers
5k views

Data structure whose name starts with the letter “N”?

-1 votes
2 answers
123 views

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

7 votes
0 answers
59 views

Tree of addition chains

0 votes
0 answers
27 views

Variants of weak optimization problems for convex sets

7 votes
1 answer
297 views

Comparing Shor's and Regev's Quantum Factoring algorithm

3 votes
0 answers
46 views

Hardness of deciding fractional chromatic number at most $k$

8 votes
1 answer
303 views

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

3 votes
1 answer
200 views

How to encode a function from an existential type

11 votes
4 answers
795 views

List of nice non-context-free languages

3 votes
0 answers
58 views

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

10 votes
2 answers
619 views

Complexity of NFA cofiniteness

0 votes
0 answers
67 views

Is every non recurvisely enumerable language is RE-hard? [closed]

0 votes
1 answer
90 views

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

0 votes
0 answers
52 views

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

-3 votes
0 answers
55 views

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

-1 votes
0 answers
53 views

NTM preserving modular number of accepting paths

-2 votes
0 answers
52 views

Graph theoretic problems complete for certain counting classes

1 vote
0 answers
151 views

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

2 votes
1 answer
378 views

A question on combinatorial algorithm

3 votes
1 answer
79 views

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

5 votes
0 answers
70 views

Hardness of Computing Tribes-DNF by Decision Trees

1 vote
0 answers
70 views

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

4 votes
0 answers
130 views

Learning a regular language with a specified closure property

0 votes
0 answers
25 views

Recognizeability of PFTM

0 votes
0 answers
46 views

cutting plane method for convex optimization

1 vote
0 answers
64 views

Perceptual similarity problem in theoretical computer science

5 votes
0 answers
87 views

Does there exist a cryptographic associative hash function?

3 votes
1 answer
109 views

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

8 votes
1 answer
236 views

Is any function between $n$ and $n\log n$ time-constructible on a 1-tape TM?

1 vote
0 answers
40 views

Practical Applications of Information Algebras


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