Skip to main content

Explore our questions

0 votes
0 answers
8 views

Interactive Proof for Graphs with No Non-Trivial Automorphisms

2 votes
1 answer
93 views

Complexity of 2-coloring with extra constraints

1 vote
1 answer
40 views

Solving #SAT through TQBF

0 votes
0 answers
19 views

Multipoint evaluation in Lagrange basis

44 votes
5 answers
7k views

What is the smallest Turing machine where it is unknown if it halts or not?

1 vote
0 answers
29 views

Classical Fourier analysis for the nonabelian hidden subgroup problem

0 votes
0 answers
19 views

Dependence of lossless compression (e.g. Lempel-Ziv) on string length and alphabet size

0 votes
1 answer
138 views

Solution to Subset Sum Problem (in some sense) using Gaussian elimination modulo 2

2 votes
0 answers
43 views

EXPSPACE-complete optimization problems

0 votes
0 answers
20 views

Reduction from any succinct language to tiling

1 vote
2 answers
135 views

Use of transitive closure in proof of NC hierarchy collapse

-2 votes
0 answers
36 views

Graphs, given a vertex find shortest even path with each of the other vertices

6 votes
1 answer
109 views

Are there any books or articles that contain information on the P weak omega or second order predicate calculi?

4 votes
1 answer
429 views

Why can't CVP be trivially reduced to SVP by shifting?

Browse more Questions