Home/Magazine Archive/April 2011 (Vol. 54, No. 4)/Technical Perspective: Patterns Hidden from Simple.../Full Text

Research highlights
# Technical Perspective: Patterns Hidden from Simple Algorithms

Is the number 9021960864034418159813 random? Educated opinions
might vary from "No! No single string can be random," to the more
contemptuous "Come on! Those are just the 714th to 733rd digits
of π." Yet, to my limited mind, the string did appear random.
Is there a way to use some formal mathematics to justify my
naïveté? The modern theory of
pseudorandomness^{2,5}
indeed manages to explain such phenomena, where strings appear
random to simple minds. The key, this theory argues, is that
randomness is really in the "eyes of the beholder," or rather in
the computing power of the tester of randomness. More things
appear random to simpler, or resource-limited, algorithms than to
complex, powerful, algorithms.

Why should we care? Because randomness is a key resource in computation. Monte Carlo simulations abound in the use of computation for prediction. On the theoretical side too, algorithms get simplified or speeded up incredibly if they use randomness. Fundamental tasks in distributed computing (such as synchronization) can be solved only with randomness. And there is no hope for maintaining privacy and secrecy without randomness. At the same time much of the randomness we deal with in reality is not "pure." They don't come as a collection of independent random bits, but are generated by other processes. Knowing how an algorithm, or a computational process, works in the presence of somewhat random strings becomes the essence of a recurring question. (For example, should you really trust nuclear power safety calculations made by a Monte-Carlo algorithm using randomness from the C++ rand program?)

Such questions get formalized in the theory of
pseudo-randomness as follows: It considers some source of
randomness *X* (formally given by some probability
distribution over *n*-bit strings), and a class of Boolean
algorithms *A* (algorithms that decide Boolean questions)
and asks if some algorithm in *A* behaves very differently
given access to a random string generated by *X*, than it
does on pure random strings? If every algorithm in *A*
behaves roughly the same on *X* as on pure randomness, we
say *X* is pseudo-random to *A.* In the example here,
*X* = X_{π} may be the source that picks a random
integer *i* between 1 and 10000 and outputs π [*i* +
1];...;π [*i* + 20] where π [*j*] denotes
the *j*th digit of π. Given some class of algorithms
*A* one could now ask, does X_{π} look
pseudo-random to *A?*

Unfortunately answering such questions leads to a fundamental
challenge in the theory of computing. Proving, say, that
X_{π} looks random to *A* involves showing that
no algorithm in *A* can *detect* patterns shown by the
digits of π. And proving that some class of algorithms can't
do some task is a major challenge to theoretical computer science
(the most notorious question being "Is **P** =
**NP**?").

Given such major obstacles to analyzing the seeming randomness
in strings, it is no surprise that the study of pseudo-randomness
remains in its infancy. The following paper by Mark Braverman
sheds new light on this field. It illustrates that a broad class
of sources, as long as they have sufficient local randomness,
fool a broad, but relatively simple, class of
algorithms—those that compute "AC^{0} functions."
AC^{0} functions are those whose input-output behavior
can be described by a Boolean logic circuit consisting *n*
input wires and polynomially many NOT gates and AND and OR gates
of arbitrary fan-in. AC^{0} functions—that
correspond to tasks computable in constant time on highly
parallel machines—are at the forefront of the class of
computational tasks that we do seem to understand. For instance,
AC^{0} functions can compute the sum of two
*n/2*-bit integers, but not their product (and so we do know
things they can't do). In fact, we even knew a explicit source of
relatively small entropy that appeared pseudo-random to this
class.^{4} Yet our understanding of the
essence of what sources fooled this class of algorithms was
unknown, leading Linial and Nisan^{3} to
conjecture that a certain form of "local randomness" was
sufficient to seem random to this class of algorithms. The local
randomness they pointed to is widely termed "limited
independence." A source *X* is said to be *k-wise*
independent if any particular *k* bits of the random source
are totally random and independent. Linial and Nisan conjectured
that for every constant depth circuit, some (log
*n*)^{O(1)} -wise independence would look like pure
*n* bits of randomness. For over two decades this conjecture
remained unresolved. Only recently,
Bazzi^{1} resolved a special case of the
conjecture (for the case of AC^{0} functions
corresponding to depth 2 circuits, or "DNF formulae").

Now Braverman's work resolves the conjecture affirmatively. In
the process he reveals novel, elegant ways in which
AC^{0} functions can be described by low-degree
multivariate polynomials, showing some of the interplay between
Boolean computation and more classical mathematics. We need to
see many more such connections before we can hope to address the
wide challenges of computational complexity (and **P** vs.
**NP**). Indeed even to address the question implied by the
opening paragraph "Are the digits of π pseudo-random to
AC^{0} functions?," one needs to understand much more.
Fortunately, Braverman's work may have reduced this question to a
purely number-theoretic one: Are the digits of π locally
random?

1. Bazzi, L.M.J. Polylogarithmic independence
can fool dnf formulas. *SIAM J. Comput. 38*, 6 (2009),
2220–2272.

2. Blum, M. and Micali, S. How to generate
cryptographically strong sequences of pseudorandom bits. *SIAM
J. on Computing 13*, 4 (Nov. 1984), 850–864.

3. Linial, N. and Nisan, N. Approximate
inclusion-exclusion. *Combinatorica 10*, 4 (1990),
349–365.

4. Nisan, N. Pseudorandom generators for
space-bounded computation. *Combinatorica 12*, 4 (1992),
449–461.

5. Yao, A.C-C. Theory and applications of
trapdoor functions (extended abstract). In *Proceedings of
FOCS* (1982). IEEE, 80–91.

**©2011
ACM 0001-0782/11/0400 $10.00**

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from permissions@acm.org or fax (212) 869-0481.

The Digital Library is published by the Association for Computing Machinery. Copyright © 2011 ACM, Inc.

No entries found