20 votes

Examples of successful derandomization from BPP to P

$SL = L$. $RL$ stands for randomized logspace and $RL=L$ is a smaller version of the problem $RP=P$. A major stepping stone was the proof of Reingold in '04 ("Undirected S-T Connectivity in Logspace")...
usul's user avatar
  • 7,615
16 votes

Examples of successful derandomization from BPP to P

There is basically only one interesting problem in BPP not known to be in P: Polynomial Identity Testing, given an algebraic circuit is the polynomial it generates identically zero. Impagliazzo and ...
Lance Fortnow's user avatar
15 votes
Accepted

What is the proof of this nonstandard version of Azuma's inequality?

I can't find a reference, so I'll just sketch the proof here. Theorem. Let $X_1, \cdots, X_n$ be real random variables. Let $a_1, \cdots, a_n, b_1, \cdots, b_n$ be constants. Suppose that, for all $i ...
Thomas's user avatar
  • 2,803
13 votes

Examples of successful derandomization from BPP to P

Besides polynomial identity testing, one other very important problem known to be in BPP but not in P is approximating the permanent of a non-negative matrix or even the number of perfect matchings in ...
Raghu Meka's user avatar
13 votes

Can true randomness (provably) be replaced with Kolmogorov randomness for RP?

I think the question being asked here is roughly "is there a sense in which we can replace the sequence of random bits in an algorithm with bits drawn deterministically from an appropriately long ...
Dylan McKay's user avatar
12 votes

Johnson and Lindenstrauss lemma for hamming space

Consider the $n$ vectors $e_1,\ldots,e_n$ of weight $1$, and the zero vector $e_0$. The Hamming distance between $e_0$ to any $e_i$ is $1$. Let $\varphi$ be a map into a Hamming cube of dimension $m$, ...
Yuval Filmus's user avatar
  • 14.5k
10 votes
Accepted

Randomness and small circuits complexity classes

Most nonuniform complexity classes—$\mathrm{NC^1}$ included—are closed under the $\mathrm{BP}$ operator by the same argument as $\mathrm{BPP\subseteq P/poly}$: using the Chernoff–Hoeffding bound, the ...
Emil Jeřábek's user avatar
10 votes

Can we fast generate perfectly uniformly mod 3 or solve NP problem?

I will use numbers starting from $0$ rather than $1$, as I find it much more natural. Here are two classes of problems we can solve in this way: Functions in TFNP (i.e., single-valued total NP search ...
Emil Jeřábek's user avatar
9 votes

List of quantum-inspired algorithms

There's also a recent work on low-rank semidefinite programming that, though not based directly on a quantum algorithm, still uses the same quantum-inspired techniques.
Ewin's user avatar
  • 91
9 votes
Accepted

Is there a linear time algorithm for integer multiplication verification?

There is a linear time randomized algorithm, that is of complexity $O(\log n)$: Cf M. Kaminski, A note on probabilistically verifying integer and polynomial products, J. ACM 36(1), pp. 142–149, Jan. ...
Bruno's user avatar
  • 4,504
8 votes
Accepted

Finding a positive point for a collection of polynomials

Yes, your problem is NP-hard, by reduction from THREE-SATISFIABILITY. THREE-SATISFIABILITY: Instance: Boolean variables $u_1,\ldots,u_n$; clauses $c_1,\ldots,c_m$ of length three over the $u_i$ ...
Gamow's user avatar
  • 5,772
8 votes
Accepted

Random sampling data structure with removal

Copying my comment on that from here: There exist published algorithms that support sampling from discrete probability distributions in O(1) time, AND modifying the distribution in O(1) time per ...
Neal Young's user avatar
  • 10.6k
8 votes
Accepted

Can the halting problem be solved probabilistically?

It is well known that any language or function computable by a probabilistic algorithm is also computable deterministically. Here, we require that with probability $>1/2$, the algorithm outputs the ...
Emil Jeřábek's user avatar
8 votes
Accepted

Randomized algorithms not based on Schwartz-Zippel

Here is a natural problem known to be in $\mathsf{BPP}$ but not $\mathsf{RP} \cup \mathsf{coRP}$, Problem 2.6 of [1]: Given a prime $p$, integers $N$ and $d$, and a list $A$ of invertible $d \times d$ ...
Joshua Grochow's user avatar
7 votes

Can we fast generate perfectly uniformly mod 3 or solve NP problem?

If you could perfectly generate mod $3$ OR solve SAT (or any other NP-complete problem, for that matter) then $NP = coNP$. In particular, consider the perfect generator / solver when given a SAT ...
daniello's user avatar
  • 3,266
7 votes

Randomized algorithms not based on Schwartz-Zippel

This is a search problem rather than a decision problem: factorization of polynomials over finite fields can be done in randomized polynomial time (TFZPP) using the Cantor–Zassenhaus algorithm, but no ...
Emil Jeřábek's user avatar
6 votes
Accepted

The relationship between degree of vertex and size of dominating set

If all vertices have degree at least $d$ then there is always a dominating set of size $\frac{n \ln n}{d} + 1$. Pick a random set $S$ of size $\frac{n \ln n}{d}$. For a particular vertex $v$, the ...
daniello's user avatar
  • 3,266
6 votes
Accepted

Can we fast generate perfectly uniformly mod 3 or solve NP problem?

As a followup to domotorp’s answer, I believe we can solve NP search problems satisfying one the following restrictions: the number of solutions is known, and not divisible by $3$; or, the number of ...
Emil Jeřábek's user avatar
6 votes
Accepted

Uniform derandomisation of circuit complexity classes

The class uniform-RNC has been studied a lot. It is an open problem whether uniform-RNC = uniform-NC. Uniform-(R)NC correspond to (randomized) PRAMs with polynomially many processors and ...
Markus Bläser's user avatar
6 votes
Accepted

List of quantum-inspired algorithms

As claimed by Leslie G. Valiant in a seminal paper 1 of his, Holographic algorithms are inspired by the quantum computational model. However, they are executable on classical computers and do not ...
Alessandro Cosentino's user avatar
6 votes
Accepted

kmeans++ for arbitrary metric spaces and general potential function

Here's an example that suggests that the stronger claim in the earlier version (Lemma 5.3) is false. I've only given a cursory look at the papers, so please check this carefully to make sure I am ...
Neal Young's user avatar
  • 10.6k
6 votes
Accepted

Converting a Bernoulli to a Gaussian

Suppose you had such a randomized procedure that takes a value in $\{-1,1\}$ and outputs a real number. Let $P$ and $Q$ be the output distribution on input $+1$ and $-1$ respectively. Consider the ...
Kunal's user avatar
  • 76
6 votes
Accepted

Trying to understand the intuition behind Yao's Minimax Principle

$\newcommand{\A}{\mathcal{A}}\newcommand{\I}{\mathcal{I}}\newcommand{\E}{\mathbb{E}}\newcommand{\C}[2]{C(I_{#1},A_{#2})}$Let $ {\mathcal I } $ be the collection of possible inputs, endowed with a $\...
Yuval Peres's user avatar
6 votes
Accepted

A question on combinatorial algorithm

[EDIT: Added second proof, using Hall's theorem.] Theorem 1. There is a poly-time algorithm for the problem. We give a direct proof, then another proof using Hall's theorem. Both proofs use the ...
Neal Young's user avatar
  • 10.6k
5 votes

The relationship between degree of vertex and size of dominating set

1) To refine daniello's answer, there is a standard bound in domination that for any graph of minimum degree $d$, there is a dominating set of size at most (roughly) $\frac{\log d}{d}n$. This bound ...
Florent Foucaud's user avatar
5 votes

Random point in a d-dimensional ball

For the latter, this discussion is a good starting point. For the former, I guess finding a random point in the ball, rounding it to a grid point, then checking that grid point is in the ball.
jjg's user avatar
  • 191
5 votes

Max cut problem between two connected subgraphs

Here is a straightforward reduction from the max-cut problem: Take any graph and add two new vertices $u,v$ and connect them to every other vertex with weight 0 and connect them to each other by a ...
Saeed's user avatar
  • 3,440
5 votes
Accepted

Correctness of AKS algorithm for shortest vector problem

What you seem to be missing is that $\tau$ is not applied to all "green" vectors. Instead, think of every point $x_i$ as having a coin attached to it. Before you use $x_i$ in the algorithm, you toss ...
Sasho Nikolov's user avatar
5 votes
Accepted

What is a very simple pseudodeterministic algorithm (for educational purposes)?

The Tonelli–Shanks algorithm for computing square roots modulo primes. More generally, factorization of polynomials over finite fields using the Cantor–Zassenhaus algorithm. Both can be made ...
Emil Jeřábek's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible