37. FOCS 1996: Burlington, Vermont, USA

• Sanjeev Arora:
  Polynomial Time Approximation Schemes for Euclidean TSP and Other Geometric Problems. 2-11
  
• Alan M. Frieze, Ravi Kannan:
  The Regularity Lemma and Approximation Schemes for Dense Problems. 12-20
  
• Sanjeev Arora, Alan M. Frieze, Haim Kaplan:
  A New Rounding Procedure for the Assignment Problem with Applications to Dense Graph Arrangement Problems. 21-30
  
• Claire Kenyon, Eric Rémila:
  Approximate Strip Packing. 31-36
  
• Christoph Dürr, Miklos Santha:
  A Decision Procedure for Unitary Linear Quantum Cellular Automata. 38-45
  
• Dorit Aharonov, Michael Ben-Or:
  Polynomial Simulations of Decohered Quantum Computers. 46-55
  
• Peter W. Shor:
  Fault-Tolerant Quantum Computation. 56-65
  
• Jon M. Kleinberg:
  Single-Source Unsplittable Flow. 68-77
  
• William H. Cunningham, James F. Geelen:
  The Optimal Path-Matching Problem. 78-85
  
• Jon M. Kleinberg, Ronitt Rubinfeld:
  Short Paths in Expander Graphs. 86-95
  
• Daniel A. Spielman, Shang-Hua Teng:
  Spectral Partitioning Works: Planar Graphs and Finite Element Meshes. 96-105
  
• Grigory Kogan:
  Computing Permanents over Fields of Characteristic 3: Where and Why It Becomes Difficult (extended abstract). 108-114
  
• Ming-Deh A. Huang, Yiu-Chung Wong:
  Solving Systems of Polynomial Congruences Modulo a Large Prime (extended abstract). 115-124
  
• Dorit Dor, Uri Zwick:
  Median Selection Requires (2+epsilon)n Comparisons. 125-134
  
• Arne Andersson:
  Faster Deterministic Sorting and Searching in Linear Space. 135-141
  
• Vijay V. Vazirani, Huzur Saran, B. Sundar Rajan:
  An Efficient Algorithm for Constructing Minimal Trellises for Codes over Finite Abelian Groups. 144-153
  
• Daniel A. Spielman:
  Highly Fault-Tolerant Parallel Computation (extended abstract). 154-163
  
• Madhu Sudan:
  Maximum Likelihood Decoding of Reed Solomon Codes. 164-172
  
• Micah Adler:
  New Coding Techniques for Improved Bandwidth Utilization. 173-182
  
• Yair Bartal:
  Probabilistic Approximations of Metric Spaces and Its Algorithmic Applications. 184-193
  
• Neal Madras, Dana Randall:
  Factoring Graphs to Bound Mixing Rates. 194-203
  
• Ravi Kannan, Guangxing Li:
  Sampling According to the Multivariate Normal Density. 204-212
  
• Michael Mitzenmacher:
  Load Balancing and Density Dependent Jump Markov Processes (extended abstract). 213-222
  
• Richard J. Anderson:
  Tree Data Structures for N-Body Simulation. 224-233
  
• Oren Etzioni, Steve Hanks, Tao Jiang, Richard M. Karp, Omid Madani, Orli Waarts:
  Efficient Information Gathering on the Internet (extended abstract). 234-243
  
• Prasad Chalasani, Somesh Jha, Isaac Saias:
  Approximate Option Pricing. 244-253
  
• Denis Thérien, Thomas Wilke:
  Temporal Logic and Semidirect Products: An Effective Characterization of the Until Hierarchy. 256-263
  
• Martin Grohe:
  Equivalence in Finite-Variable Logics is Complete for Polynomial Time. 264-273
  
• Paul Beame, Toniann Pitassi:
  Simplified and Improved Resolution Lower Bounds. 274-282
  
• Michael O. Rabin:
  Computationally Hard Algebraic Problems (extended abstract). 284-289
  
• Joseph Cheriyan, Ramakrishna Thurimella:
  Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching (extended abstract). 292-301
  
• Naveen Garg:
  A 3-Approximation for the Minimum Tree Spanning k Vertices. 302-309
  
• Guy Even, Joseph Naor, Leonid Zosin:
  An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem. 310-319
  
• Süleyman Cenk Sahinalp, Uzi Vishkin:
  Efficient Approximate and Dynamic Matching of Patterns Using a Labeling Paradigm (extended abstract). 320-328
  
• Avrim Blum, Alan M. Frieze, Ravi Kannan, Santosh Vempala:
  A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions. 330-338
  
• Oded Goldreich, Shafi Goldwasser, Dana Ron:
  Property Testing and Its Connection to Learning and Approximation. 339-348
  
• Amos Beimel, Francesco Bergadano, Nader H. Bshouty, Eyal Kushilevitz, Stefano Varricchio:
  On the Applications of Multiplicity Automata in Learning. 349-358
  
• Alan M. Frieze, Mark Jerrum, Ravi Kannan:
  Learning Linear Transformations. 359-368
  
• Friedhelm Meyer auf der Heide, Christian Scheideler:
  Deterministic Routing with Bounded Buffers: Turning Offline into Online Protocols. 370-379
  
• Matthew Andrews, Baruch Awerbuch, Antonio Fernández, Jon M. Kleinberg, Frank Thomson Leighton, Zhiyong Liu:
  Universal Stability Results for Greedy Contention-Resolution Protocols. 380-389
  
• Andrei Z. Broder, Alan M. Frieze, Eli Upfal:
  A General Approach to Dynamic Packet Routing with Bounded Buffers (extended abstract). 390-399
  
• Yuval Rabani:
  Path Coloring on the Mesh. 400-409
  
• Roy Armoni, Michael E. Saks, Avi Wigderson, Shiyu Zhou:
  Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles. 412-421
  
• Manindra Agrawal, Thomas Thierauf:
  The Boolean Isomorphism Problem. 422-430
  
• Kazuyuki Amano, Akira Maruoka:
  Potential of the Approximation Method (extended abstract). 431-440
  
• Arne Andersson, Peter Bro Miltersen, Søren Riis, Mikkel Thorup:
  Static Dictionaries on AC⁰ RAMs: Query Time Theta(sqrt(log n/log log n)) is Necessary and Sufficient. 441-450
  
• Dorit Dor, Shay Halperin, Uri Zwick:
  All Pairs Almost Shortest Paths. 452-461
  
• Monika Rauch Henzinger, Satish Rao, Harold N. Gabow:
  Computing Vertex Connectivity: New Bounds from Old Techniques. 462-471
  
• Jeff Erickson:
  Better Lower Bounds for Halfspace Emptiness. 472-481
  
• Pankaj K. Agarwal, Edward F. Grove, T. M. Murali, Jeffrey Scott Vitter:
  Binary Search Partitions for Fat Rectangles. 482-491
  
• Erez Petrank, Gábor Tardos:
  On the Knowledge Complexity of NP. 494-503
  
• Ran Canetti, Rosario Gennaro:
  Incoercible Multiparty Computation (extended abstract). 504-513
  
• Mihir Bellare, Ran Canetti, Hugo Krawczyk:
  Pseudorandom Functions Revisited: The Cascade Construction and Its Concrete Security. 514-523
  
• Noga Alon, Dmitry N. Kozlov, Van H. Vu:
  The Geometry of Coin-Weighing Problems. 524-532
  
• Thomas M. Cover:
  Universal Data Compression and Portfolio Selection. 534-538
  
• Tracy Kimbrel, Anna R. Karlin:
  Near-Optimal Parallel Prefetching and Caching. 540-549
  
• Matthew Andrews, Michael A. Bender, Lisa Zhang:
  New Algorithms for the Disk Scheduling Problem. 550-559
  
• Lars Arge, Jeffrey Scott Vitter:
  Optimal Dynamic Interval Management in External Memory (extended abstract). 560-569
  
• C. Greg Plaxton, Rajmohan Rajaraman:
  Fast Fault-Tolerant Concurrent Access to Shared Objects. 570-579
  
• Yonatan Aumann, Michael A. Bender:
  Fault Tolerant Data Structures. 580-589
  
• Funda Ergün, Ravi Kumar, Ronitt Rubinfeld:
  Approximate Checking of Polynomials and Functional Equations (extended abstract). 592-601
  
• Ravi Kumar, D. Sivakumar:
  Efficient Self-Testing/Self-Correction of Linear Recurrences. 602-611
  
• Sridhar Rajagopalan, Leonard J. Schulman:
  Verifying Identities (extended abstract). 612-616
  
• Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson:
  Gadgets, Approximation, and Linear Programming (extended abstract). 617-626
  
• Johan Håstad:
  Clique is Hard to Approximate Within n^1-epsilon. 627-636
  

Last update Sat May 18 18:30:56 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page