Skip to main content

Top Questions

5 votes
2 answers
247 views

What are the computations model with a constant slowdown ? (and why do we care about Turing machines)

4 votes
1 answer
451 views

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

7 votes
1 answer
249 views

Is parity of GI easy?

4 votes
1 answer
199 views

Complexity of permutation group intersection

-1 votes
1 answer
176 views

How close is a Boolean function from being a linear boolean function?

1 vote
2 answers
145 views

Use of transitive closure in proof of NC hierarchy collapse

2 votes
1 answer
132 views

Complexity of 2-coloring with extra constraints

3 votes
3 answers
111 views

Can parametricity be applied to show a property of function values?

-1 votes
1 answer
67 views

why is there the need for a reduction between clique and multicoloured clique?

4 votes
1 answer
85 views

Solving #SAT through TQBF

1 vote
0 answers
124 views

Testing monotonicity for functions of the form $f :\{0,1,2\}^n\rightarrow \{0,1\}$

6 votes
0 answers
94 views

How large are the Brzozowski Derivatives?

2 votes
1 answer
90 views

Classical Fourier analysis for the nonabelian hidden subgroup problem

3 votes
0 answers
98 views
+50

Collapse of query and oracle hierarchies

2 votes
1 answer
57 views

Is $D_\infty$ a universal domain?

0 votes
1 answer
70 views

Are Turing Machines Models?

2 votes
0 answers
88 views

Minimizing a submodular function containing summation and production under partition matroid constraint

3 votes
0 answers
85 views

References for $\mathsf{PSPACE} \neq \mathsf{E}$ and $\mathsf{P} \neq \mathsf{NTIME}(n^k)$

1 vote
2 answers
65 views

Can a RAM machine with polynomial memory be simulated by a multi-tape Turing machine without extra time or space costs?

3 votes
0 answers
80 views

What does Håstad verifier query?

2 votes
0 answers
76 views

Multipoint evaluation in Lagrange basis

-2 votes
0 answers
65 views

Parallel complexity of modular inverse of $2^t\pm i$

4 votes
0 answers
61 views

EXPSPACE-complete optimization problems

4 votes
0 answers
60 views

Problems hard on toroidal graphs that are polytime on planar

0 votes
1 answer
54 views

An efficient way to find windows of size m with at least k identities

-2 votes
0 answers
48 views

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

-1 votes
1 answer
45 views

is the set of all numbers that sum up a subset sum problem a one way function?

0 votes
0 answers
40 views

What rules govern when combinators (e.g. S, K, and I) can be only partially applied?

2 votes
0 answers
39 views

Subsuming Learned Clauses

2 votes
0 answers
37 views

Work-efficient parallelization of matrix chain multiplication?

1 vote
0 answers
37 views

Contraction in belief revision

-1 votes
0 answers
34 views

Applying $/mu$-Operator for Unbounded minimization

-2 votes
0 answers
34 views

Big O of evaluating expression under RAM model

1 vote
0 answers
34 views

Clause Density for guaranteed Easy (2, 3) SAT Cases

0 votes
0 answers
32 views

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

0 votes
0 answers
31 views

Reduction from any succinct language to tiling

2 votes
1 answer
21 views

Complexity of finding graph automorphism group vs. canonization

1 vote
0 answers
23 views

On generating tight instances of Max Cover / NP-hard Problems

0 votes
0 answers
22 views

What would be the time/approx.-complexity of making a special graph into hole-free?

1 vote
0 answers
22 views

Bounds on the problematic number of threads

0 votes
0 answers
21 views

NP-completeness of Nested Flexible Machine Scheduling with summaric job completion time


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