Turbo's user avatar
Turbo's user avatar
Turbo's user avatar
Turbo
  • Member for 13 years, 6 months
  • Last seen this week
37 votes
5 answers
2k views

Integer multiplication when one integer is fixed

22 votes
5 answers
844 views

Easy problems with hard counting versions

20 votes
2 answers
1k views

Barriers to show $P=NP$

20 votes
0 answers
637 views

Identifying Reducible/Irreducible polynomials over $Z[x]$

16 votes
2 answers
617 views

New algorithm for Discrete log and its implications for Quantum computing

15 votes
2 answers
349 views

Approximation in subexponental time

15 votes
1 answer
869 views

Is there a quantum NC algorithm for computing GCD?

14 votes
1 answer
451 views

What would signify hierarchy collapse to first level?

13 votes
4 answers
3k views

Applications of $p$-adic numbers in CS

12 votes
2 answers
1k views

Sensitivity-Block sensitivity conjecture - Implications

12 votes
2 answers
1k views

List of number theoretic or algebraic problems in various complexity classes

11 votes
2 answers
2k views

Representing boolean function by a polynomial

11 votes
1 answer
538 views

Matrix rigidity and uses of matrices with low rigidity

11 votes
2 answers
1k views

Determinants and Matrix Multiplication - Similarity and differences in algorithmic complexity and arithmetic circuit size

11 votes
1 answer
271 views

Is deciding whether changing one entry decreases the permanent of a matrix in the polynomial hierarchy?

10 votes
1 answer
442 views

An obstruction like ETH

10 votes
1 answer
485 views

Proofs in $S_{2}^{1}$

10 votes
2 answers
815 views

Cancellation and determinant

10 votes
2 answers
1k views

Determinant of a generalized Vandermonde matrix

10 votes
2 answers
1k views

Deciding graph homomorphism

10 votes
1 answer
718 views

Lovasz theta function and regular graphs (odd cycles in particular) - connections to spectral theory

10 votes
1 answer
449 views

On derandomizing polynomial identity testing

9 votes
1 answer
1k views

True Bit Complexity of matrix multiplication is $O(n^{4})$

9 votes
2 answers
441 views

Barriers to separating other complexity classes

9 votes
1 answer
338 views

Evidence for $\mathsf{P} \neq \mathsf{PP}$ if the polynomial hierarchy collapses?

9 votes
1 answer
1k views

Intersection of languages in NP

8 votes
1 answer
280 views

Is there a name for this concept in Communication Complexity?

8 votes
1 answer
1k views

On the sensitivity conjecture?

8 votes
0 answers
392 views

A canonical complete problem for EXP and NEXP in terms of formulae

8 votes
2 answers
482 views

Spectral techniques for genus of a graph

1
2 3 4 5
11