36. FOCS 1995: Milwaukee, Wisconsin, USA

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

Last update Fri May 25 08:14:15 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page