acm-header
Sign In

Communications of the ACM

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 pseudorandomness2,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 jth 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 "AC0 functions." AC0 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. AC0 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, AC0 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 Nisan3 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, Bazzi1 resolved a special case of the conjecture (for the case of AC0 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 AC0 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 AC0 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?

Back to Top

References

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.

Back to Top

Author

Madhu Sudan ([email protected]) is a Principal Researcher at Microsoft Research New England and the Fujitsu Professor of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology.

Back to Top

Footnotes

DOI: http://doi.acm.org/10.1145/1924421.1924445


©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 [email protected] or fax (212) 869-0481.

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


 

No entries found

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account
Article Contents: