William Aiello

SODA Conference 2003 Conference Paper

Dynamic routing on networks with fixed-size buffers

• William Aiello
• Rafail Ostrovsky
• Eyal Kushilevitz
• Adi Rosén

FOCS Conference 2001 Conference Paper

Random Evolution in Massive Graphs

• William Aiello
• Fan R. K. Chung
• Linyuan Lu

Many massive graphs (such as the WWW graph and Call graphs) share certain universal characteristics which can be described by the so-called "power law. " In this paper, we, examine three important aspects of power law graphs, (1) the evolution of power law graphs, (2) the asymmetry of in-degrees and out-degrees, (3) the "scale invariance" of power law graphs. In particular, we give three increasingly general directed graph models and one general undirected graph model for generating power law graphs by adding at most one node and possibly one or more edges at a time. We show that for any given edge density and desired power laws for in-degrees and out-degrees, not necessarily the same, the resulting graph will almost surely have the desired edge density and the power laws for the in-degrees and out-degrees. Our most general directed and undirected models include nearly all known power law evolution models as special cases. Finally, we show that our evolution models generate "scale invariant" graphs. We describe a method for scaling the time in our evolution model such that the power law of the degree sequences remains invariant.

STOC Conference 2000 Conference Paper

A random graph model for massive graphs

• William Aiello
• Fan R. K. Chung
• Linyuan Lu

STOC Conference 1998 Conference Paper

Adaptive Packet Routing for Bursty Adversarial Traffic

• William Aiello
• Eyal Kushilevitz
• Rafail Ostrovsky
• Adi Rosén

SODA Conference 1995 Conference Paper

Design of Practical and Provably Good Random Number Generators (Extended Abstract)

• William Aiello
• Sivaramakrishnan Rajagopalan
• Ramarathnam Venkatesan

STOC Conference 1995 Conference Paper

Knowledge on the average-perfect, statistical and logarithmic

• William Aiello
• Mihir Bellare
• Ramarathnam Venkatesan

STOC Conference 1993 Conference Paper

Approximate load balancing on dynamic and asynchronous networks

• William Aiello
• Baruch Awerbuch
• Bruce M. Maggs
• Satish Rao

SODA Conference 1991 Conference Paper

Learning the Fourier Spectrum of Probabilistic Lists and Trees

• William Aiello
• Milena Mihail

FOCS Conference 1987 Conference Paper

Perfect Zero-Knowledge Languages Can Be Recognized in Two Rounds

• William Aiello
• Johan Håstad

A hierarchy of probabilistic complexity classes generalizing NP has recently emerged in the work of [Ba], [GMR], and [GS]. The IP hierarchy is defined through the notion of an interactive proof system, in which an all powerful prover tries to convince a probabilistic polynomial time verifier that a string w is in a language L. The verifier tosses coins and exchanges messages back and forth with the prover before he decides whether to accept w. This proof-system yields "probabilistic" proofs: the verifier may erroneously accept or reject w with small probability. In [GMR] such a protocol was defined to be a zero-knowledge protocol if at the end of the interaction the verifier has learned nothing except that w ∈ L. We study complexity theoretic implications of a language having this property. In particular we prove that if L admits a zeroknowledge proof then L can also be recognized by a two round interactive proof. This complements a result by Fortnow [F] where it is proved that the complement of L has a two round interactive proof protocol. The methods of proof are quite similar to those of Fortnow [F]. As in his case the proof works under the assumption that the original protocol is only zero-knowledge with respect to a specific verifier.

FOCS Conference 1986 Conference Paper

On the Power of Interaction

• William Aiello
• Shafi Goldwasser
• Johan Håstad

A hierarchy of probabilistic complexity classes generalizing NP has recently emerged in the work of [B], [GMR], and [GS]. The IP hierarchy is defined through the notion of an interactive proof system, in which an all powerful prover tries to convince a probabilistic polynomial time verifier that a string x is in a language L. The verifier tosses coins and exchanges messages back and forth with the prover before he decides whether to accept x. This proof-system yields "probabilistic" proofs: the verifier may erroneously accept or reject x with small probability. The class IP[f(|x|)] is said to contain L if, there exists an interactive proof system with f(|x|)- message exchanges (interactions) such that with high probability the verifier accepts x if and only if x ε L. Babai [B] showed that all languages recognized by interactive proof systems with bounded number of interactions, can be recognized by interactive proof systems with only two interactions. Namely, for every constant k, IP[k] collapses to Ip[2]. In this paper, we give evidence that interactive proof systems with unbounded number of interactions may be more powerful than interactive proof systems with bounded number of interactions. We show that for any unbounded function f(n) there exists an oracle B such that IPB [f(|x|)] ⊄ PHB. This implies that IPB[f(n)] ≠ IPB[2], since IPB[2] ⊆ Π2B for all oracles B. The techniques employed are extensions of the techniques for proving lower bounds on small depth circuits used in [FSS], [Y] and [H1].