default search action
36th FOCS 1995: Milwaukee, Wisconsin, USA
- 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995. IEEE Computer Society 1995, ISBN 0-8186-7183-1
- 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
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 N. Vorobjov Jr.:
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 E. 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(S3/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 Lp 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.3446n): 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 Kahalé
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
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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-11-15 19:20 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: