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