Papers
- Paul Valiant, Testing Symmetric Properties of Distributions,
STOC 2008.
We introduce the notion of a Canonical Tester for a class of properties on distributions, that is, a tester strong and general enough that "a distribution property in the class is testable if and only if the Canonical Tester tests it''. We construct a Canonical Tester for the class of symmetric properties of one or two distributions, satisfying a certain weak continuity condition. Analyzing the performance of the Canonical Tester on specific properties resolves several open problems, establishing lower bounds that match known upper bounds: we show that distinguishing between entropy $<\alpha$ or $>\beta$ on distributions over $[n]$ requires $n^{\alpha/\beta- o(1)}$ samples, and distinguishing whether a pair of distributions has statistical distance $<\alpha$ or $>\beta$ requires $n^{1- o(1)}$ samples. Our techniques also resolve a conjecture about a property that our Canonical Tester does not apply to: distinguishing identical distributions from those with statistical distance $>\beta$ requires $\Omega(n^{2/3})$ samples.A probabilistically checkable proof (PCP) system enables proofs to be veried in time polylogarithmic in the length of a classical proof. Computationally sound (CS) proofs improve upon PCPs by additionally shortening the length of the transmitted proof to be polylogarithmic in the length of the classical proof.
[abstract] [bib] [pdf]@inproceedings{Val:testing08, title = "Testing Symmetric Properties of Distributions", author = "Paul Valiant", booktitle = "Proceedings of STOC", year = "2008" }
- Paul Valiant, Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency,
Theory of Cryptography Conference 2008 (winner of best student paper award).
A probabilistically checkable proof (PCP) system enables proofs to be veried in time polylogarithmic in the length of a classical proof. Computationally sound (CS) proofs improve upon PCPs by additionally shortening the length of the transmitted proof to be polylogarithmic in the length of the classical proof.
In this paper we explore the ultimate limits of non-interactive proof systems with respect to time and space effciency. We present a proof system where the prover uses space polynomial in the space of a classical prover and time essentially linear in the time of a classical prover, while the verier uses time and space that are essentially constant. Further, this proof system is composable: there is an algorithm for merging two proofs of length k into a proof of the conjunction of the original two theorems in time polynomial in k, yielding a proof of length exactly k.
We deduce the existence of our proposed proof system by way of a natural new assumption about proofs of knowledge. In fact, a main contribution of our result is showing that knowledge can be "traded" for time and space effciency in noninteractive proof systems. We motivate this result with an explicit construction of noninteractive CS proofs of knowledge in the random oracle model.
[abstract] [bib] [pdf]@inproceedings{Val:csproofs08, title = "Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency", author = "Paul Valiant", booktitle = "Proceedings of TCC", year = "2008" }
- Xi Chen, Shang-Hua Teng, and Paul Valiant, The Approximation Complexity of Win-Lose Games,
SODA 2007.
We further our algorithmic and structural understanding of Nash equilibria. Specifically:
-- We distill the hard core of the complexity of Nash equilibria, showing that even correctly computing a logarithmic number of bits of the equilibrium strategies of a two-player win-lose game is as hard as the general problem.
-- We prove the following structural result about Nash equilibria: “the set of approximate equilibria of a zero-sum game is convex.”
[abstract] [bib] [pdf]@inproceedings{CTV:approxwinlose07, title = "The Approximation Complexity of Win-Lose Games", author = "Xi Chen and Shang-Hua Teng and Paul Valiant", booktitle = "Proceedings of SODA", year = "2007" }
- Mythili Vutukuru, Paul Valiant, Swastik Kopparty, and Hari Balakrishnan How to Construct a Correct and Scalable iBGP Configuration,
INFOCOM 2006.
The Internet's current interdomain routing protocol, BGP (Border Gateway Protocol), has two modes of operation: eBGP (external BGP), used to exchange routing information between autonomous systems, and iBGP (internal BGP), used to propagate that information within an autonomous system (AS). In a ``full mesh'' iBGP configuration, every router has a BGP session with every border router in the AS. Because a full mesh configuration has a large number of iBGP sessions and does not scale well, configurations based on route reflectors are commonly used for intra-AS route dissemination. Unfortunately, route reflector configurations violate important correctness properties, including loop-free forwarding and complete visibility to all eBGP-learned best routes, especially in the face of router and link failures. This paper presents and analyzes the first (to our knowledge) algorithm, BGPSep, to construct an iBGP session configuration that is both correct and more scalable than a full mesh. BGPSep uses the notion of a graph separator - a small set of nodes whose removal partitions a graph into connected components of roughly equal sizes - to choose route reflectors and iBGP sessions in a way that guarantees correctness. We evaluate an implementation of the BGPSep algorithm on several real-world and simulated network topologies and find that iBGP configurations generated by BGPSep have between 2.5 to 5 times fewer iBGP sessions than a full mesh.
[abstract] [bib] [pdf]@inproceedings{VVKB2006iBGP, author = "Mythili Vutukuru and Paul Valiant and Swastik Kopparty and Hari Balakrishnan", title = "How to Construct a Correct and Scalable iBGP Configuration", booktitle = "IEEE INFOCOM", year = "2006", month = "April", address = "Barcelona, Spain" }
- Paul Valiant, The Tensor Product of Two Codes Is Not Necessarily Robustly Testable,
APPROX-RANDOM 2005.
There has been significant interest lately in the task of constructing codes that are testable with a small number of random probes. Ben-Sasson and Sudan show that the repeated tensor product of codes leads to a general class of locally testable codes. One question that is not settled by their work is the local testability of a code generated by a single application of the tensor product. Special cases of this question have been studied in the literature in the form of "tests for bivariate polynomials", where the tensor product has been shown to be locally testable for certain families of codes. However the question remained open for the tensor product of generic families of codes. Here we resolve the question negatively, giving families of codes whose tensor product does not have good local testability properties.
[abstract] [bib] [pdf]@inproceedings{Val:tensorcodes05, title = "The Tensor Product of Two Codes Is Not Necessarily Robustly Testable", author = "Paul Valiant", booktitle = "Proceedings of APPROX-RANDOM", year = "2005" }
- Timothy Abbot, Daniel Kane, Paul Valiant, On the Complexity of Two-Player Win-Lose Games,
FOCS 2005 (co-winner of the best student paper award).
The efficient computation of Nash equilibria is one of the most formidable challenges in computational complexity today. The problem remains open for two-player games.
We show that the complexity of two-player Nash equilibria is unchanged when all outcomes are restricted to be 0 or 1. That is, win-or-lose games are as complex as the general case for two-player games.
[abstract] [bib] [pdf]@inproceedings{AKV:winlosegames05, title = "On the Complexity of Two-Player Win-Lose Games", author = "Timothy Abbot and Daniel Kane and Paul Valiant", booktitle = "Proceedings of the 46th FOCS", year = "2005", pages = "113--122" }
- Mart de Graaf, Paul Valiant, Polynomial Representations of Symmetric Partial Boolean Functions,
SIAM J. Discrete Math 19(2):481-488.
For Boolean polynomials in Z_p of sufficiently low degree we derive a relation expressing their values on one level set in terms of their values on another level set. We use this relation to derive linear upper and lower bounds, tight to within constant factor, on the degrees of various approximate majority functions, namely functions that take the value 0 on one level set, the value 1 on a different level set, and arbitrary 0-1 values on other Boolean inputs. We show sub-linear upper bounds in the case of moduli that are not prime powers.
[abstract] [bib] [pdf]@article{GV:polynomialreps05, title = "Polynomial Representations of Symmetric Partial Boolean Functions", author = "Mart de Graaf and Paul Valiant", journal = "SIAM J. Discrete Math", year = "2005", volume = "19", number = "2", pages = "481--488" }
Drafts
- Constantinos Daskalakis, Grant Schoenebeck, Gregory Valiant, and Paul Valiant, On the Complexity of Nash Equilibria of Action-Graph Games,
We consider the problem of computing Nash Equilibria of action-graph games (AGGs). AGGs, introduced by Bhat and Leyton-Brown, is a succinct representation of games that encapsulates both ‘local’dependencies as in graphical games, and partial indifference to other agents’ identities as in anonymous games, which occur in many natural settings. This is achieved by specifying a graph on the set of actions, so that the payoff of an agent for selecting a strategy depends only on the number of agents playing each of the neighboring strategies in the action graph. We present a Polynomial Time Approximation Scheme for computing mixed Nash equilibria of AGGs with constant treewidth and a constant number of agent types (and an arbitrary number of strategies), together with hardness results for the cases when either the treewidth or the number of agent types is unconstrained. In particular, we show that even if the action graph is a tree, but the number of agent-types is unconstrained, it is NP–complete to decide the existence of a pure-strategy Nash equilibrium and PPAD-complete to compute a mixed Nash equilibrium (even an approximate one); similarly for symmetric AGGs (all agents belong to a single type), if we allow arbitrary treewidth. These hardness results suggest that, in some sense, our PTAS is as strong of a positive result as one can expect.
[abstract] [bib] [arXiv]@inproceedings{DSVV:actiongraph08, title = "On the Complexity of Nash Equilibria of Action-Graph Games", author = "Constantinos Daskalakis and Grant Schoenebeck and Gregory Valiant and Paul Valiant", year = "2008", booktitle = "submitted", }