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")...
- 7,595
18
votes
Accepted
Generalizing the "median trick" to higher dimensions?
What you're looking for is almost the same a robust central tendency: a way of reducing a cloud of data points to a single point, such that if many of the data points are close to some "ground truth" ...
- 50.9k
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 ...
- 8,616
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 ...
- 2,803
14
votes
Generalizing the "median trick" to higher dimensions?
This is a neat question and I've thought about it before. Here's what we came up with:
You run your algorithm $n$ times to get outputs $x_1, \cdots, x_n \in \mathbb{R}^d$ and you know what with high ...
- 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 ...
- 131
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 ...
- 548
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$, ...
- 14.3k
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 ...
- 16.9k
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 ...
- 16.9k
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.
- 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. ...
- 4,439
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$
...
- 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 ...
- 9,595
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 ...
- 16.9k
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$ ...
- 36.9k
7
votes
Generalizing the "median trick" to higher dimensions?
There is a notion of the median of a set of points in high-dimensions and general norms which is known under various names. It is just the point that minimizes the sum of distances to all the points ...
- 881
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 ...
- 3,256
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 ...
- 16.9k
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 ...
- 3,256
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 ...
- 16.9k
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 ...
- 2,878
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 ...
- 3,960
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 ...
- 9,595
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 ...
- 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 $\...
- 441
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 ...
- 2,143
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.
- 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 ...
- 3,440
Only top scored, non community-wiki answers of a minimum length are eligible