Blog Archives

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