Randomized Computation

Randomness is used in computation to design algorithms which are simpler, more efficient, or parallelizable. A randomized algorithm produces outputs based on not only the inputs but also random choices. A probabilistic Turing machine (PTM) is a deterministic Turing machine

Tagged with: ,
Posted in Theory

Valiant-Vazirani Theorem

Consider the following promise problem: Given a boolean formula that has at most one satisfying assignment, decide whether it is unsatisfiable or it has exactly one satisfying assignment. The Valiant-Vazirani theorem says that, if this problem is solvable in polynomial

Tagged with: ,
Posted in Theory

Lower Bounds Against Circuits with Modular Gates

The modular gate MODm, for any integer $$m$$, outputs 0 if the sum of its inputs is 0 modulo $$m$$, and outputs 1 otherwise. An ACC[m] circuit is a circuit with NOT gates and unbounded fan-in AND, OR, and MODm

Tagged with: ,
Posted in Theory

Combinatorial Design and Pseudorandom Generator

For a set of size $$l$$, choose $$m$$ subsets each of size $$n$$ such that each pair of subsets has intersection size at most $$d$$. This gives a combinatorial design with parameters $$(m,l,n,d)$$. That is, we have \(I_1,\ldots, I_m \subseteq

Tagged with: , ,
Posted in Theory