36. FOCS 1995:
Milwaukee,
Wisconsin
36th Annual Symposium on Foundations of Computer Science,
Milwaukee, Wisconsin, 23-25 October 1995. IEEE Computer Society
- Leslie G. Valiant:
Cognitive Computation (Extended Abstract).
2-3 BibTeX
- Satyanarayana V. Lokam:
Spectral Methods for Matrix Rigidity with Applications to Size-Depth Tradeoffs and Communication Complexity.
6-15 BibTeX
,
- Noam Nisan, Avi Wigderson:
Lower Bounds for Arithmetic Circuits via Partial Serivatives (Preliminary Version).
16-25 BibTeX
- Kenneth W. Regan, D. Sivakumar, Jin-yi Cai:
Pseudorandom Generators, Measure Theory, and Natural Proofs.
26-35 BibTeX
- Armin Haken:
Counting Bottlenecks to Show Monotone P <=> NP.
36-40 BibTeX
- Benny Chor, Oded Goldreich, Eyal Kushilevitz, Madhu Sudan:
Private Information Retrieval.
41-50 BibTeX
- Jon M. Kleinberg, Éva Tardos:
Disjoint Paths in Densely Embedded Graphs.
52-61 BibTeX
- Guy Even, Joseph Naor, Satish Rao, Baruch Schieber:
Divide-and-Conquer Approximation Algorithms via Spreading Metrics (Extended Abstract).
62-71 BibTeX
- Randeep Bhatia, Samir Khuller, Joseph Naor:
The Loading Time Scheduling Problem (Extended Abstract).
72-81 BibTeX
- Leslie A. Hall:
Approximability of Flow Shop Scheduling.
82-91 BibTeX
,
- András A. Benczúr:
A Representation of Cuts within 6/5 Times the Edge Connectivity with Applications.
92-102 BibTeX
- Mike Paterson, Aravind Srinivasan:
Contention Resolution with Bounded Delay.
104-113 BibTeX
- C. Greg Plaxton:
Tight Bounds for a Distributed Selection Game with Applications to Fixed-Connection Machines.
114-122 BibTeX
- John H. Reif:
Efficient Parallel Solution of Sparse Eigenvalue and Eigenvector Problems.
123-132 BibTeX
- Pascal Koiran:
Approximating the Volume of Definable Sets.
134-141 BibTeX
- Paul Dagum, Richard M. Karp, Michael Luby, Sheldon M. Ross:
An Optimal Algorithm for Monte Carlo Estimation (Extended Abstract).
142-149 BibTeX
- Michael Luby, Dana Randall, Alistair Sinclair:
Markov Chain Algorithms for Planar Lattice Structures (Extended Abstract).
150-159 BibTeX
- Sanjeev Mahajan, Ramesh Hariharan:
Derandomizing Semidefinite Programming Based Approximation Algorithms.
162-169 BibTeX
- Moni Naor, Omer Reingold:
Synthesizers and Their Application to the Parallel Construction of Psuedo-Random Functions.
170-181 BibTeX
- Moni Naor, Leonard J. Schulman, Aravind Srinivasan:
Splitters and Near-Optimal Derandomization.
182-191 BibTeX
- Eric Torng:
A Unified Analysis of Paging and Caching.
194-203 BibTeX
- Rakesh D. Barve, Edward F. Grove, Jeffrey Scott Vitter:
Application-Controlled Paging for a Shared Cache (Extended Abstract).
204-213 BibTeX
- Bala Kalyanasundaram, Kirk Pruhs:
Speed is as Powerful as Clairvoyance.
214-221 BibTeX
- Mihalis Yannakakis:
Perspectives on Database Theory.
224-246 BibTeX
- Herbert Edelsbrunner:
Algebraic Decompositions of Non-Convex Polyhedra.
248-257 BibTeX
- Dima Grigoriev, Marek Karpinski, Nicolai Vorobjov:
Improved Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees.
258-265 BibTeX
- Tamal K. Dey, Sumanta Guha:
Optimal Algorithms for Curves on Surfaces.
266-274 BibTeX
- Alexander I. Barvinok:
Integral Geometry of Higher-Dimensional Polytopes and the Average Case in Combinatorial Optimization.
275-283 BibTeX
- Joachim von zur Gathen, Igor Shparlinski:
Finding Points on Curves over Finite Fields (Extended Abstract).
284-292 BibTeX
- Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan:
Learning Polynomials with Queries: The Highly Noisy Case.
294-303 BibTeX
- Nader H. Bshouty, Yishay Mansour:
Simple Learning Algorithms for Decision Trees and Multivariate Polynomials.
304-311 BibTeX
- Peter Auer, Manfred K. Warmuth:
Tracking the Best Disjunction.
312-321 BibTeX
- Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, Robert E. Schapire:
Gambling in a Rigged Casino: The Adversarial Multi-Arm Bandit Problem.
322-331 BibTeX
- Yoav Freund, Michael J. Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire:
Efficient Algorithms for Learning to Play Repeated Games Against Computationally Bounded Adversaries.
332-341 BibTeX
- Michael E. Saks, Shiyu Zhou:
RSPACE(S) \subseteq DSPACE(S3/2).
344-353 BibTeX
- Mitsunori Ogihara:
Sparse P-Hard Sets Yield Space-Efficient Algorithms.
354-361 BibTeX
- Jin-yi Cai, D. Sivakumar:
The Resolution of a Hartmanis Conjecture.
362-371 BibTeX
- F. Frances Yao, Alan J. Demers, Scott Shenker:
A Scheduling Model for Reduced CPU Energy.
374-382 BibTeX
- Baruch Awerbuch, Yossi Azar, Edward F. Grove, Ming-Yang Kao, P. Krishnan, Jeffrey Scott Vitter:
Load Balancing in the Lp Norm.
383-391 BibTeX
- Amos Fiat, Yishay Mansour, Adi Rosén, Orli Waarts:
Competitive Access Time via Dynamic Storage Rearrangement (Preliminary Version).
392-401 BibTeX
- Sanjeev Arora:
Reductions, Codes, PCPs, and Inapproximability.
404-413 BibTeX
- Martin Fürer:
Improved Hardness Results for Approximating the Chromatic Number.
414-421 BibTeX
- Mihir Bellare, Oded Goldreich, Madhu Sudan:
Free Bits, PCPs and Non-Approximability - Towards Tight Results.
422-431 BibTeX
- Mihir Bellare, Don Coppersmith, Johan Håstad, Marcos A. Kiwi, Madhu Sudan:
Linearity Testing in Characteristic Two.
432-441 BibTeX
- Richard Beigel, David Eppstein:
3-Coloring in Time O(1.3446n): A No-MIS Algorithm.
444-452 BibTeX
- Monika Rauch Henzinger, Thomas A. Henzinger, Peter W. Kopke:
Computing Simulations on Finite and Infinite Graphs.
453-462 BibTeX
- C. R. Subramanian:
Minimum Coloring Random and Semi-Random Graphs in Polynomial Expected Time.
463-472 BibTeX
- Miklós Ajtai, Nimrod Megiddo, Orli Waarts:
Improved Algorithms and Analysis for Secretary Problems and Generalizations.
473-482 BibTeX
- Jean-Claude Latombe:
Controllability, Recognizability, and Complexity Issues in Robot Motion Planning.
484-500 BibTeX
- Alon Orlitsky, James R. Roche:
Coding for Computing.
502-511 BibTeX
- Noga Alon, Jeff Edmonds, Michael Luby:
Linear Time Erasure Codes with Nearly Optimal Recovery (Extended Abstract).
512-519 BibTeX
- Harry Buhrman, Lance Fortnow, Leen Torenvliet:
Using Autoreducibility to Separate Complexity Classes.
520-527 BibTeX
- John Watrous:
On One-Dimensional Quantum Cellular Automata.
528-537 BibTeX
- Russell Impagliazzo:
Hard-Core Distributions for Somewhat Hard Problems.
538-545 BibTeX
- Milena Mihail, Christos Kaklamanis, Satish Rao:
Efficient Access to Optical Bandwidth - Wavelength Routing on Directed Fiber Trees, Rings, and Trees of Rings.
548-557 BibTeX
- Richard Cole, Bruce M. Maggs, Ramesh K. Sitaraman:
Routing on Butterfly Networks with Random Faults.
558-570 BibTeX
- Richard Beigel, William Hurwood, Nabil Kahale:
Fault Diagnosis in a Flash.
571-580 BibTeX
- Sridhar Hannenhalli, Pavel A. Pevzner:
Transforming Men into Mice (Polynomial Algorithm for Genomic Distance Problem).
581-592 BibTeX
- Robert Beals:
Algorithms for Matrix Groups and the Tits Alternative.
593-602 BibTeX
- Paolo Ferragina, Roberto Grossi:
Optimal On-Line Search and Sublinear Time Update in String Matching.
604-612 BibTeX
- Dimitris Margaritis, Steven Skiena:
Reconstructing Strings from Substrings in Rounds.
613-620 BibTeX
- Richard M. Karp, Orli Waarts, Geoffrey Zweig:
The Bit Vector Intersection Problem (Preliminary Version).
621-630 BibTeX
- S. Rao Kosaraju:
Faster Algorithms for the Construction of Parameterized Suffix Trees (Preliminary Version).
631-637 BibTeX
- Michelangelo Grigni, Elias Koutsoupias, Christos H. Papadimitriou:
An Approximation Scheme for Planar Graph TSP.
640-645 BibTeX
- Chris Okasaki:
Amortization, Lazy Evaluation, and Persistence: Lists with Catenation via Lazy Linking.
646-654 BibTeX
- Arne Andersson:
Sublogarithmic Searching without Multiplications.
655-663 BibTeX
- Monika Rauch Henzinger, Valerie King:
Fully Dynamic Biconnectivity and Transitive Closure.
664-672 BibTeX
- Amos Beimel, Anna Gál, Mike Paterson:
Lower Bounds for Monotone Span Programs.
674-681 BibTeX
- Matthias Krause, Pavel Pudlák:
On Computing Boolean Functions by Sparse Real Polynomials.
682-691 BibTeX
- Paul Beame, Russell Impagliazzo, Toniann Pitassi:
Improved Depth Lower Vounds for Small Distance Connectivity.
692-701 BibTeX
- Shay Kutten, David Peleg:
Tight Fault Locality (Extended Abstract).
704-713 BibTeX
- Eric Schenk:
Faster Approximate Agreement with Multi-Writer Registers.
714-723 BibTeX
- Zvi Galil, Alain J. Mayer, Moti Yung:
Resolving Message Complexity of Byzantine Agreement and beyond.
724-733 BibTeX
Copyright © Sat May 16 23:12:26 2009
by Michael Ley (ley@uni-trier.de)
