user avatar
user avatar
user avatar
Geoffrey Irving
  • Member for 9 years, 7 months
  • Last seen this week
16 votes

Should reductions make us more or less optimistic for the tractability of a problem?

4 votes
Accepted

Is deterministic pseudorandomness possibly stronger than randomness in parallel?

3 votes
Accepted

Complexity of generically inverting a class of near linear monotonic functions

3 votes

Nontrivial algorithm for computing a sliding window median

3 votes
Accepted

Minimum communication cost for zero knowledge proofs of three colorability

3 votes

Find the cheapest cycle through two points on a rectangular grid

3 votes

Probability that a random sorting network works

3 votes

Can one prove the discovery of a P versus NP solution without actually revealing it?

2 votes

Is prime-counting function #P-complete?

2 votes

Minimum communication cost for zero knowledge proofs of three colorability

2 votes

Higher order Quines - when do super Quines exist?

2 votes
Accepted

Smoothly leaking information over time

2 votes

How fast can we compute the set inclusion poset of a set family?

1 vote

Number of operations to compute product of pairwise sums over a commutative semiring

1 vote

Is this constrained planar triangulation algorithm $O(m \log m)$?

1 vote

Does the infinite graph of diagonals have an infinite component?

1 vote

Does the infinite graph of diagonals have an infinite component?

1 vote
Accepted

Quantum complexity of TQBF with an untrusted oracle

1 vote
Accepted

Complexity of matrix diagonalization

0 votes
Accepted

Error correction that adapts to different error rates

-3 votes

What kind of theoretical object corresponds to a C++ concept?