Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs
Joe Bebel's user avatar
Joe Bebel's user avatar
Joe Bebel's user avatar
Joe Bebel
  • Member for 12 years, 1 month
  • Last seen more than a month ago
  • University of Southern California
43 votes
Accepted

Is it a rule that discrete problems are NP-hard and continuous problems are not?

21 votes
Accepted

Time complexity with irrational exponent?

15 votes
Accepted

How much would a SAT oracle help speeding up polynomial time algorithms?

12 votes

Finding the sparsest solution to a system of linear equations

11 votes

Is there a natural problem in quasi-polynomial time, but not in polynomial time?

10 votes

Is a quadratic nondeterminism speed-up of deterministic computation plausible?

10 votes

For which problems in P is it easier to verify the result than to find it?

8 votes

Obituaries of dead conjectures

8 votes

Is graph isomorphism still open for bounded clique width or bounded rank width? 2015 paper claims it is polynomial

7 votes

Polynomial-time reductions between undecidable languages

7 votes

Can we confirm that 2-SAT can indeed be transformed into Horn-SAT in this manner?

7 votes

Proof for Kolmogorov complexity is uncomputable using reductions

7 votes

Why is lambda calculus so "function" oriented?

7 votes
Accepted

possible bridge between group growth theory and complexity theory?

7 votes
Accepted

Deterministic Randomness Extractors

4 votes
Accepted

Popular average-case complexity assumptions

3 votes
Accepted

What is a "level-r pseudo expectation functional"?

3 votes

Are nearly all natural numbers compressible?

2 votes

Does the infinite graph of diagonals have an infinite component?

2 votes

Submatrix of small rank

2 votes

Is there a gap amplification type of result for the Graph Isomorphism Problem?

1 vote

Can a measurement commuting with the stabilizer of a state disturb the state?

1 vote
Accepted

Algorithm to determine if given algorithm runs in polynomial time

1 vote

Numerical precision in sum-of-squares method?