| Foreword |
| Conference Organization and Program Committee |
| Reviewers |
| Machine Learning: My Favorite Results, Directions, and Open Problems / A. BlumTutorial 1： |
| Mixing / D. RandallTutorial 2： |
| Performance Analysis of Dynamic Network Processes / E. UpfalTutorial 3： |
| A Polynomial Algorithm for Recognizing Perfect Graphs / G. Cornuejols ; X. Liu ; K. VuskovicSession 1： |
| On Certain Connectivity Properties of the Internet Topology / M. Mihail ; C. Papadimitriou ; A. Saberi |
| Paths, Trees, and Minimum Latency Tours / K. Chaudhuri ; B. Godfrey ; S. Rao ; K. Talwar |
| Approximation Algorithms for Orienteering and Discounted-Reward TSP / S. Chawla ; D. Karger ; T. Lane ; A. Meyerson ; M. Minkoff |
| Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs / H. Kaplan ; M. Lewenstein ; N. Shafrir ; M. Sviridenko |
| On the Implementation of Huge Random Objects / O. Goldreich ; S. Goldwasser ; A. NussboimSession 2： |
| Zero-Knowledge Sets / S. Micali ; M. Rabin ; J. Kilian |
| Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography / J. Kamp ; D. Zuckerman |
| On the (In)security of the Fiat-Shamir Paradigm / Y. Kalai |
| Locally Testable Cyclic Codes / L. Babai ; A. Shpilka ; D. StefankovicSession 3： |
| List Decoding Using the XOR Lemma / L. Trevisan |
| On [eta]-Biased Generators in NC[superscript 0] / E. Mossel |
| Proving Hard-Core Predicates Using List Decoding / A. Akavia ; S. Safra |
| Instability of FIFO at Arbitrarily Low Rates in the Adversarial Queueing Model / R. Bhattacharjee ; A. GoelSession 4： |
| Proofs of the Parisi and Coppersmith-Sorkin Conjectures for the Finite Random Assignment Problem / C. Nair ; B. Prabhakar ; M. Sharma |
| Always Good Turing: Asymptotically Optimal Probability Estimation / A. Orlitsky ; N. Santhanam ; J. Zhang |
| Learning DNF from Random Walks / N. Bshouty ; R. O'Donnell ; R. Servedio |
| Quantum Search of Spatial Regions / S. Aaronson ; A. AmbainisSession 5： |
| A Lattice Problem in Quantum NP / D. Aharonov ; O. Regev |
| A Lower Bound for Bounded Round Quantum Communication Complexity of Set Disjointness / R. Jain ; J. Radhakrishnan ; P. Sen |
| Polynomial Degree vs. Quantum Query Complexity |
| An In-Place Sorting with O(n log n) Comparisons and O(n) Moves / G. Franceschini ; V. GeffertSession 6： |
| Breaking a Time-and-Space Barrier in Constructing Full-Text Indices / W.-K. Hon ; K. Sadakane ; W.-K. Sung |
| I/O-Efficient Strong Connectivity and Depth-First Search for Directed Planar Graphs / L. Arge ; N. Zeh |
| The Cost of Cache-Oblivious Searching / M. Bender ; G. Brodal ; R. Fagerberg ; D. Ge ; S. He ; H. Hu ; J. Iacono ; A. Lopez-Ortiz |
| Tight Lower Bounds for the Distinct Elements Problem / P. Indyk ; D. Woodruff |
| Hardness of Approximating the Shortest Vector Problem in High L[subscript p] Norms / S. KhotSession 7： |
| More on Average Case vs Approximation Complexity / M. Alekhnovich |
| On Worst-Case to Average-Case Reductions for NP Problems / A. Bogdanov |
| Rank Bounds and Integrality Gaps for Cutting Planes Procedures / J. Buresh-Oppenheim ; N. Galesi ; S. Hoory ; A. Magen ; T. Pitassi |
| The Resolution Complexity of Random Constraint Satisfaction Problems / M. Molloy ; M. SalavatipourSession 8： |
| Algorithms and Complexity Results for #SAT and Bayesian Inference / F. Bacchus ; S. Dalmao |
| Linear Upper Bounds for Random Walk on Small Density Random 3-CNFs / E. Ben-Sasson |
| On the Maximum Satisfiability of Random Formulas / D. Achlioptas ; A. Naor ; Y. Peres |
| Logics for Reasoning about Cryptographic Constructions / R. Impagliazzo ; B. KapronSession 9： |
| Lower Bounds for Non-Black-Box Zero Knowledge / B. Barak ; Y. Lindell ; S. Vadhan |
| General Composition and Universal Composability in Secure Multi-Party Computation |
| Bounded-Concurrent Secure Two-Party Computation in a Constant Number of Rounds / R. Pass ; A. Rosen |
| Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time O(m[superscript 1.31]) / D. Spielman ; S.-H. TengSession 10： |
| Separating the Power of Monotone Span Programs over Different Fields / A. Beimel ; E. Weinreb |
| A Group-Theoretic Approach to Fast Matrix Multiplication / H. Cohn ; C. Umans |
| Symmetric Polynomials over Z[subscript m] and Simultaneous Communication Protocols / N. Bhatnagar ; P. Gopalan ; R. Lipton |
| Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm / L. Becchetti ; S. Leonardi ; A. Marchetti-Spaccamela ; G. Schafer ; T. VredeveldSession 11： |
| Stability and Efficiency of a Random Local Load Balancing Protocol / A. Anagnostopoulos ; A. Kirsch |
| Gossip-Based Computation of Aggregate Information / D. Kempe ; A. Dobra ; J. Gehrke |
| Broadcasting Algorithms in Radio Networks with Unknown Topology / A. Czumaj ; W. Rytter |
| Switch Scheduling via Randomized Edge Coloring / G. Aggarwal ; R. Motwani ; D. Shah ; A. Zhu |
| On the Impossibility of Dimension Reduction in l1 / B. Brinkman ; M. CharikarSession 12： |
| Clustering with Qualitative Information / V. Guruswami ; A. Wirth |
| Bounded Geometries, Fractals, and Low-Distortion Embeddings / A. Gupta ; R. Krauthgamer ; J. Lee |
| On Levels in Arrangements of Curves, II: A Simple Inequality and Its Consequences / T. Chan |
| The Complexity of Homomorphism and Constraint Satisfaction Problems Seen from the Other Side / M. GroheSession 13： |
| Towards a Dichotomy Theorem for the Counting Constraint Satisfaction Problem / A. Bulatov ; V. Dalmau |
| Towards a Characterization of Truthful Combinatorial Auctions / R. Lavi ; A. Mu'alem ; N. NisanSession 14： |
| Group Strategyproof Mechanisms via Primal-Dual Algorithms / M. Pal ; E. Tardos |
| The Value of Knowing a Demand Curve: Bounds on Regret for Online Posted-Price Auctions / R. Kleinberg ; T. Leighton |
| Approximation Via Cost-Sharing: A Simple Approximation Algorithm for the Multicommodity Rent-or-Buy Problem / A. Kumar ; T. Roughgarden |
| A Non-Markovian Coupling for Randomly Sampling Colorings / T. Hayes ; E. VigodaSession 15： |
| The Ising Model on Trees: Boundary Conditions and Mixing Time / F. Martinelli ; A. Sinclair ; D. Weitz |
| Logconcave Functions: Geometry and Efficient Sampling Algorithms / L. Lovasz ; S. Vempala |
| Simulated Annealing in Convex Bodies and an O*(n[superscript 4]) Volume Algorithm |
| Author Index |
| Foreword |
| Conference Organization and Program Committee |
| Reviewers |
| Machine Learning: My Favorite Results, Directions, and Open Problems / A. BlumTutorial 1： |
| Mixing / D. RandallTutorial 2： |
| Performance Analysis of Dynamic Network Processes / E. UpfalTutorial 3： |
図書
19th Annual Symposium on Foundations of Computer Science, Oct. 16-18, 1978, Ann Arbor, Michigan
