| Foreword |
| Conference Organization and Program Committee |
| Reviewers |
| Quantum Weak Coin-Flipping with Bias of 0.192 / C. MochonSession 1： |
| Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs / H. Klauck ; R. Spalek ; R. de Wolf |
| Quantum Walk Algorithm for Element Distinctness / A. Ambainis |
| Quantum Speed-Up of Markov Chain Based Algorithms / M. Szegedy |
| Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation / D. Aharonov ; W. van Dam ; J. Kempe ; Z. Landau ; S. Lloyd ; O. Regev |
| Maximizing Quadratic Programs: Extending Grothendieck's Inequality / M. Charikar ; A. WirthSession 2： |
| An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem / L. Lau |
| Edge-Disjoint Paths in Planar Graphs / C. Chekuri ; S. Khanna ; F. Shepherd |
| Machine Minimization for Scheduling Jobs with Interval Constraints / J. Chuzhoy ; S. Guha ; J. Naor |
| Random Edge Can Be Exponential on Abstract Cubes / J. Matousek ; T. SzaboSession 3： |
| On the Integrality Ratio for Asymmetric TSP / M. Goemans ; H. Karloff |
| The Hardness of Metric Labeling |
| Hardness of Buy-at-Bulk Network Design / M. Andrews |
| Hardness of Approximating the Shortest Vector Problem in Lattices / S. KhotSession 4： |
| Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique |
| Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs? / G. Kindler ; E. Mossel ; R. O'Donnell |
| Assignment Testers: Towards a Combinatorial Proof of the PCP-Theorem / I. Dinur ; O. Reingold |
| Cryptography in NC[superscript 0] / B. Applebaum ; Y. Ishai ; E. KushilevitzSession 5： |
| An Unconditional Study of Computational Zero Knowledge / S. Vadhan |
| Universally Composable Protocols with Relaxed Set-Up Assumptions / B. Barak ; R. Canetti ; J. Nielsen ; R. Pass |
| On the (Im)possibility of Cryptography with Imperfect Randomness / Y. Dodis ; S. Ong ; M. Prabhakaran ; A. Sahai |
| Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity / B. Dean ; J. VondrakSession 6： |
| An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design / A. Gupta ; R. Ravi ; A. Sinha |
| Stochastic Optimization is (Almost) as easy as Deterministic Optimization / D. Shmoys ; C. Swamy |
| O([radical]log n) Approximation to SPARSEST CUT in O(n[superscript 2]) Time / S. Arora ; E. Hazan ; S. Kale |
| Maximum Matchings via Gaussian Elimination / M. Mucha ; P. Sankowski |
| Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game / R. Savani ; B. von StengelSession 7： |
| Edge Pricing of Multicommodity Networks for Heterogeneous Selfish Users / G. Karakostas ; S. Kolliopoulos |
| Tolls for Heterogeneous Selfish Users in Multicommodity Networks and Generalized Congestion Games / L. Fleischer ; K. Jain ; M. Mahdian |
| A Polynomial Time Algorithm for Computing the Arrow-Debreu Market Equilibrium for Linear Utilities |
| The Price of Stability for Network Design with Fair Cost Allocation / E. Anshelevich ; A. Dasgupta ; J. Kleinberg ; E. Tardos ; T. Wexler ; T. Roughgarden |
| Holographic Algorithms (Extende Abstract) / L. ValiantSession 8： |
| Hierarchy Theorems for Probabilistic Polynomial Time / L. Fortnow ; R. Santhanam |
| Private Codes or Succinct Random Codes That Are (Almost) Perfect / M. Langberg |
| On the List and Bounded Distance Decodibility of the Reed-Solomon Codes (Extended Abstract) / Q. Cheng ; D. Wan |
| Multilinear-NC[subscript 1 not equal]Multilinear-NC[subscript 2] / R. RazSession 9： |
| Algebras with Polynomial Identities and Computing the Determinant / S. Chien ; A. Sinclair |
| Lattice Problems in NP [intersection of]coNP |
| Worst-Case to Average-Case Reductions Based on Gaussian Measures / D. Micciancio |
| Extracting Randomness Using Few Independent Sources / R. Impagliazzo ; A. WigdersonSession 10： |
| Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed / A. Gabizon ; R. Shaltiel |
| Constructing Expander Graphs by 2-Lifts and Discrepancy vs. Spectral Gap / Y. Bilu ; N. Linial |
| Testing Polynomials over General Fields / T. Kaufman ; D. Ron |
| Testing Low-Degree Polynomials over Prime Fields / C. Jutla ; A. Patthak ; A. Rudra ; D. Zuckerman |
| Measured Descent: A New Embedding Method for Finite Metrics / R. Krauthgamer ; J. Lee ; M. Mendel ; A. NaorSession 11： |
| Triangulation and Embedding Using Small Sets of Beacons / A. Slivkins |
| A Simple Linear Time (1 + [varepsilon])-Approximation Algorithm for k-Means Clustering in Any Dimensions / A. Kumar ; Y. Sabharwal ; S. Sen |
| On the Power of Discrete and of Lexicographic Helly-Type Theorems / N. Halman |
| An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching / A. Chakrabarti |
| Dynamic Optimality--Almost / E. Demaine ; D. Harmon ; J. Iacono ; M. PatrascuSession 12： |
| No Sorting? Better Searching! / G. Franceschini ; R. Grossi |
| Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs / L. Roditty ; U. Zwick |
| Dynamic Transitive Closure via Dynamic Matrix Inverse (Extended Abstract) |
| Dynamic Speed Scaling to Manage Energy and Temperature / N. Bansal ; T. Kimbrel ; K. PruhsSession 13： |
| Optimal Power-Down Strategies / J. Augustine ; S. Irani |
| On the Streaming Model Augmented with a Sorting Primitive / G. Aggarwal ; M. Datar ; S. Rajagopalan ; M. Ruhl |
| Approximating Edit Distance Efficiently / Z. Bar-Yossef ; T. Jayram ; R. Kumar |
| Strong Spatial Mixing for Lattice Graphs with Fewer Colours / L. Goldberg ; R. Martin ; M. PatersonSession 14： |
| Shuffling by Semi-Random Transpositions / Y. Peres |
| Randomly Coloring Constant Degree Graphs / M. Dyer ; A. Frieze ; T. Hayes ; E. Vigoda |
| The Exact Satisfiability Threshold for a Potentially Intractible Random Constraint Satisfaction Problem / H. Connamacher ; M. Molloy |
| Spectral Analysis of Random Graphs with Skewed Degree Distributions / J. Hopcroft ; F. McSherrySession 15： |
| Learning with Errors in Answers to Membership Queries (Extended Abstract) / L. Bisht ; N. Bshouty ; L. Khoury |
| Learnability and Automatizability / M. Alekhnovich ; M. Braverman ; V. Feldman ; A. Klivans ; T. Pitassi |
| Author Index |
| Foreword |
| Conference Organization and Program Committee |
| Reviewers |
| Quantum Weak Coin-Flipping with Bias of 0.192 / C. MochonSession 1： |
| Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs / H. Klauck ; R. Spalek ; R. de Wolf |
| Quantum Walk Algorithm for Element Distinctness / A. Ambainis |
図書
19th Annual Symposium on Foundations of Computer Science, Oct. 16-18, 1978, Ann Arbor, Michigan
