Talks are held in the Gates Building, near the Main Quad of Stanford's campus. Click here for directions.
Quint and Shubik conjectured in 1994 that nondegenerate n x n bimatrix games have at most 2^n-1 equilibria, which is the case for the simple ``coordination game'' where each player's payoffs are given by the identity matrix. We present a class of counterexamples to this conjecture for n=6 (with a game that has 75 equilibria) and all n>7, with asymptotically more than 2.414^n equilibria. Compared with the earlier lower bound of 2^n, this is not far from the upper bound of about 2.6^n known from the Upper Bound Theorem for polytopes. This suggests that algorithms for determining all equilibria are best implemented using vertex enumeration. Our construction is based on cyclic polytopes with a suitable permutation of their ``facet labels'' that are used to represent the complementarity condition of an equilibrium.
The talk will emphasize the geometric intuition behind the construction. No prior knowledge of the technical concepts is required.
Email:
stengel@inf.ethz.ch
WWW:
http://www.inf.ethz.ch/personal/stengel
Related paper:
ftp://ftp.inf.ethz.ch/pub/publications/tech-reports/2xx/264.ps.gz
One of the outstanding questions in the theory of NP-completeness is the twenty year old Berman-Hartmanis conjecture. The conjecture states that all the sets complete for NP under polynomial time reductions are polynomial time isomorphic. In this talk, we prove the Berman-Hartmanis conjecture for AC^0 reductions: all sets complete for NP under AC^0 reductions are AC^0 isomorphic. Thus, all the thousands of NP-complete sets encountered in the literature are AC^0 (depth 3) isomorphic.
What makes our result possible is a technique to reduce the complexity of any AC^0 reduction between two NP-complete sets to something almost trivial to compute and invert. The new, simpler reduction is a subtle transformation of the original, requiring application of the Hastad Switching Lemma.
We also give a construction for what is (to the best of our knowledge) the first NP-complete set for which there is no AC^0 reduction from Satisfiability.
More formally, we show three theorems that hold for any complexity class C closed under (uniform) TC^0-computable many-one reductions.
(This is joint work with M. Agrawal, W. Allender, R. Impagliazzo, and T. Pitassi)
Email:
rudich@CS.cmu.EDU
WWW:
http://www.cs.cmu.edu/~rudich
Related paper:
http://www.cs.cmu.edu/~rudich/papers/reducing_reductions.ps
Our models our based on considering the behavior of limiting systems where the number of processors goes to infinity. The limiting systems can be shown to accurately describe the behavior of sufficiently large systems, and simulations demonstrate that they are reasonably accurate even for systems with a small number of processors. Our studies of specific models demonstrate the importance of using randomness to break symmetry in these systems and yield important rules of thumb for system design. The most significant result is that only small amounts of load information can be extremely useful in these settings; for example, having incoming tasks choose the least loaded of two randomly chosen processors is extremely effective over a large range of possible system parameters. In contrast, using global information can actually degrade performance unless used correctly; for example, unlike most settings where the load information is current, having tasks go to the least loaded server can significantly hurt performance.
Email:
michaelm@pa.dec.com
WWW:
http://www.research.digital.com/SRC/personal/michaelm/home.html
Related paper:
http://www.research.digital.com/SRC/personal/michaelm/WORK/old.ps
This is joint work with Monika Henzinger (Digital SRC) and Serge Plotkin (Stanford University).
Email:
agoel@cs.stanford.edu
WWW:
http://www-cs-students.stanford.edu/~agoel
Related paper:
http://www-cs-students.stanford.edu/~agoel/selective-multicast.ps
Email:
eli@cs.ucla.edu
WWW:
http://www.cs.ucla.edu/csd-lanai/fweb/eli.html
Related paper: http://www.cs.ucla.edu/csd-lanai/fweb/eli/podc2col.ps
(This is joint work with Sanjeev Khanna.)
Email:
liberato@bothrops.rutgers.edu
WWW:
http://paul.rutgers.edu/~liberato/
We obtain the following result. We show that any finite metric of size $n$ can be probabilistically approximated by $O(n \log n)$ trees such that the distortion of any edge is at most a factor of $O(\log n \log \log n)$. Further the trees and the associated probability distribution can be constructed efficiently in polynomial time. The implications of the result are twofold. First, the construction gives alternate proofs of the constructions of Bartal. Second, the polynomial size of the space we are sampling from enables us to derandomize any approximation algorithm based on above construction. We obtain the first deterministic approximation algorithms for several problems including group Steiner trees, $k$-median, buy-at-bulk network design, minimum communication spanning trees, and vehicle routing. For the group Steiner problem we derandomize the rounding scheme of Garg et al. who give a randomized approximation algorithm for solving the problem on trees.
In this talk I will describe the above construction and time permitting the derandomization scheme for group Steiner problem on trees.
This talk is based on a paper with Moses Charikar, Ashish Goel and Sudipto Guha to appear in STOC 98, and recent improvements with the above and Serge Plotkin.
Email:
chekuri@cs.stanford.edu
WWW:
http://Theory.Stanford.EDU/~chekuri/
Is it possible to encode an n bit classical input x into k qbits, s.t.
for ANY $v=v(x)$ and
for ANY $1 \le i \le n$
a decoder can recover $x_i$ from $v=v(x)$ with success probability of at least 1/2+epsilon. We call such a scheme an n->k encoding with epsilon advantage.
In other words: Instead of asking how much information can be obtained from k qbits, we ask how much information can be put into k qbits, s.t. each part of it is accessible.
Indeed, a simple example shows that a 2->1 encoding with success probability of 0.86.. exists. We prove that no classical 2->1 encoding with any positive advantage exists, thus showing a fundamental difference between classical and quantum encodings.
In the talk I'll present a proof that even in the quantum world, there is no way to encode n -> n/clog(n) with a constant advantage. One notable variant of the problem which is not covered by our proof, is the variant where we replace the requirement "for any 1 \le i \le n$ with the weaker requirement "for MOST i, 1 \le i \le n". We do not know yet whether this is a technical detail, to be fixed by a better proof, or not.We point out that this might have implications to a new model we define, QNP (for "QUANTUM NP").
This work is joint work with Umesh Vazirani.
Email:
amnon@ICSI.Berkeley.EDU
WWW:
http://www.icsi.berkeley.edu/~amnon/
An exciting new result by Ajtai, proved the equivalence of average-case and worst-case complexity of unique-SVP, a variant of these problems. Ajtai-Dwork consequently presented a crypto-system based on unique-SVP and proved that breaking it implies approximating unique-SVP to within some polynomial factor. These results stress the significance of finding the hardness of these lattice problems.
We show (using the PCP characterization of NP [RaSa, DFKRS]) that approximating CVP to within an almost-polynomial factor is NP-hard. The SVP problem has only recently been shown to be NP-hard [Ajtai]. On the other hand Goldreich and Goldwasser showed that approximating CVP and SVP up to a $\sqrt{dim}$ factor is in $co-AM$, and is therefore unlikely to be NP-hard. It was already known [ABSS] that approximating CVP up to an almost-polynomial factor is {\it quasi-NP-hard}, i.e. implies $NP \subset P^{poly-log}$.
Joint work with G. Kindler and S. Safra.
Email:
dinur@math.tau.ac.il
WWW:
Related paper:
We show that such an Intermemory is possible and present a framework for the design of an Intermemory. We also consider certain aspects of the design in greater detail. In particular, the aspects of addressing, space efficiency, and redundant coding are discussed.
(joint work with Peter N. Yianilos)
Email:
avg@research.nj.nec.com
WWW:
http://www.neci.nj.nec.com/homepages/avg/
Related paper:
In this talk I will present two algorithmic results for the approximate version that significantly improve the known bounds:
(a) preprocessing cost polynomial in n and d, and a query time polynomial in log n and d,
(b) preprocessing cost O(dn^{1+1/epsilon}) and a query time O(dn^{1/epsilon}) (for epsilon > 1),
We will also discuss experimental results indicating that the second algorithm offers significant improvement on running times over real data sets. We discuss its applications to information retrieval, pattern recognition, dynamic closest-pairs, and fast clustering algorithms.
This is joint work with Aris Gionis (the experimental part) and Rajeev Motwani.
Email:
indyk@cs.stanford.edu
WWW:
http://theory.stanford.edu/~indyk/
Related paper:
Email:
vazirani@cc.gatech.edu
WWW:
http://www.cc.gatech.edu/people/home/kjain/
Related paper:
- polynomials;
- algebraic functions;
- Boolean functions;
- linear recurrent sequences;
coinciding with values of the discrete logarithm modulo a prime $p$ at sufficiently many points (the number of points can be as little as $p^{1/2 +\varepsilon}$). These functions are considered over the residue ring modulo $p$ and over the residue ring modulo an arbitrary divisor $d$ of $p-1$. The case of $d=2$ is of special interest since it corresponds to the representation of the rightmost bit of the discrete logarithm and defines whether the argument is a quadratic residue.
These results are used to obtain lower bounds on the parallel arithmetic and Boolean complexity of computing the discrete logarithm.
The method is based on bounds of character sums and numbers of solutions of some polynomial equations.
Similar results are obtained for breaking the Diffie--Hellman cryptosystem.
Email:
igor@mpce.mq.edu.au
WWW: http://www.comp.mq.edu.au/~igor
Related paper:
Joint work with Matt Blaze and Joan Feigenbaum from AT&T Labs
Email:
naor@wisdom.weizmann.ac.il
WWW:
http://www.wisdom.weizmann.ac.il/~naor/
Related paper:
http://www.wisdom.weizmann.ac.il/~naor/PAPERS/smart.ps
Email:
feige@wisdom.weizmann.ac.il
WWW:
http://www.wisdom.weizmann.ac.il/~feige/
Related paper: