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

Integer multiplication when one integer is fixed

21 votes
5 answers
800 views

Easy problems with hard counting versions

20 votes
2 answers
1k views

Barriers to show $P=NP$

20 votes
0 answers
619 views

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

16 votes
2 answers
595 views

New algorithm for Discrete log and its implications for Quantum computing

15 votes
2 answers
344 views

Approximation in subexponental time

14 votes
1 answer
827 views

Is there a quantum NC algorithm for computing GCD?

14 votes
1 answer
433 views

What would signify hierarchy collapse to first level?

12 votes
2 answers
1k views

List of number theoretic or algebraic problems in various complexity classes

12 votes
2 answers
1k views

Sensitivity-Block sensitivity conjecture - Implications

11 votes
4 answers
2k views

Applications of $p$-adic numbers in CS

11 votes
1 answer
526 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
265 views

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

10 votes
1 answer
431 views

An obstruction like ETH

10 votes
1 answer
451 views

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

10 votes
2 answers
761 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
692 views

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

10 votes
2 answers
2k views

Representing boolean function by a polynomial

10 votes
1 answer
388 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
408 views

Barriers to separating other complexity classes

9 votes
1 answer
330 views

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

8 votes
1 answer
1k views

On the sensitivity conjecture?

8 votes
0 answers
273 views

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

8 votes
1 answer
274 views

Is there a name for this concept in Communication Complexity?

8 votes
2 answers
467 views

Spectral techniques for genus of a graph

8 votes
2 answers
3k views

Applications of computer science in biology

1
2 3 4 5
10