default search action
33rd FOCS 1992: Pittsburgh, Pennsylvania, USA
- 33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, USA, 24-27 October 1992. IEEE Computer Society 1992, ISBN 0-8186-2900-2
- Sanjeev Arora, Shmuel Safra
:
Probabilistic Checking of Proofs; A New Characterization of NP. 2-13 - Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy:
Proof Verification and Hardness of Approximation Problems. 14-23 - Noam Nisan
Undirected Connectivity in O(log ^1.5 n) Space. 24-29 - Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz:
The Isomorphism Conjecture Holds Relative to an Oracle. 30-39 - Adam L. Buchsbaum, Rajamani Sundar, Robert Endre Tarjan:
Data Structural Bootstrapping, Linear Path Compression, and Catenable Heap Ordered Double Ended Queues. 40-49 - Monika Rauch:
Fully Dynamic Biconnectivity in Graphs. 50-59 - David Eppstein, Zvi Galil, Giuseppe F. Italiano, Amnon Nissenzweig:
Sparsification-A Technique for Speeding up Dynamic Graph Algorithms (Extended Abstract). 60-69 - Tsan-sheng Hsu:
On Four-Connecting a Triconnected Graph (Extended Abstract). 70-79 - Pankaj K. Agarwal, David Eppstein, Jirí Matousek:
Dynamic Half-Space Reporting, Geometric Optimization, and Minimum Spanning Trees. 80-89 - Ketan Mulmuley:
Randomized Geometric Algorithms and Pseudo-Random Generators (Extended Abstract). 90-100 - Goos Kant:
Drawing Planar Graphs Using the lmc-Ordering (Extended Abstract). 101-110 - Eugene M. Luks:
Computing in Solvable Matrix Groups. 111-120 - Mark Giesbrecht:
Fast Algorithms for Matrix Normal Forms. 121-130 - Dario Bini, Victor Y. Pan:
Improved Parallel Polynomial Division and Its Extensions. 131-136 - James Aspnes, Orli Waarts:
Randomized Consensus in Expected O(n log ^2 n) Operations Per Processor. 137-146 - Yonatan Aumann, Michael O. Rabin:
Clock Construction in Fully Asynchronous Parallel Systems and PRAM Simulation (Extended Abstract). 147-156 - Prasad Jayanti, Tushar Deepak Chandra, Sam Toueg:
Fault-tolerant Wait-free Shared Objects. 157-166 - Erich Grädel, Gregory L. McColm:
Hierarchies in Transitive Closure Logic, Stratified Datalog and Infinitary Logic. 167-176 - Rajeev Alur, Thomas A. Henzinger:
Back to the Future: Towards a Theory of Timed Regular Languages. 177-186 - Toniann Pitassi, Alasdair Urquhart:
The Complexity of the Hajós Calculus. 187-196 - Avrim Blum, Howard J. Karloff, Yuval Rabani
A Decomposition Theorem and Bounds for Randomized Server Problems. 197-207 - Anna R. Karlin, Steven J. Phillips, Prabhakar Raghavan:
Markov Paging (Extended Abstract). 208-217 - Yossi Azar, Andrei Z. Broder, Anna R. Karlin:
On-line Load Balancing (Extended Abstract). 218-225 - C. Greg Plaxton, Bjorn Poonen
Improved Lower Bounds for Shellsort. 226-235 - Peter Bro Miltersen, Mike Paterson, Jun Tarui:
The Asymptotic Complexity of Merging Networks. 236-246 - Zvi Galil, Kunsoo Park:
Truly Alphabet-Independent Two-Dimensional Pattern Matching. 247-256 - Moshe Dubiner, Uri Zwick:
Amplification and Percolation. 258-267 - Andrew Chi-Chih Yao:
Algebraic Decision Trees and Euler Characteristics. 268-277 - Vince Grolmusz
Separating the Communication Complexities of MOD m and MOD p Circuits. 278-287 - Don Coppersmith, Baruch Schieber:
Lower Bounds on the Depth of Monotone Arithmetic Computations (Extended Summary). 288-295 - Nabil Kahalé
On the Second Eigenvalue and Linear Expansion of Regular Graphs. 296-303 - Yuri Rabinovich, Alistair Sinclair, Avi Wigderson:
Quadratic Dynamical Systems (Preliminary Version). 304-313 - Joel Friedman
On the Bit Extraction Problem. 314-319 - Mark Jerrum, Umesh V. Vazirani:
A Mildly Exponential Approximation Algorithm for the Permanent. 320-326 - Ran El-Yaniv, Amos Fiat, Richard M. Karp, G. Turpin:
Competitive Analysis of Financial Games. 327-333 - Noga Alon, Gil Kalai, Moty Ricklin, Larry J. Stockmeyer:
Lower Bounds on the Competitive Ratio for Mobile User Tracking and Distributed Job Scheduling (Extended Abstract). 334-343 - Yair Bartal, Adi Rosén:
The Distributed k-Server Problem-A Competitive Distributed Translator for k-Server Algorithms. 344-353 - Jerzy Marcinkowski, Leszek Pacholski:
Undecidability of the Horn-Clause Implication Problem. 354-362 - Dexter Kozen, Jens Palsberg, Michael I. Schwartzbach:
Efficient Inference of Partial Types. 363-371 - Jan Van den Bussche
On the Completeness of Object-Creating Query Languages (Extended Abstract). 372-379 - Hans-Peter Lenhof, Michiel H. M. Smid:
Enumerating the k Closest Pairs Optimally. 380-386 - Kenneth L. Clarkson:
Safe and Effective Determinant Evaluation. 387-395 - Naoki Katoh, Takeshi Tokuyama
On Minimum and Maximum Spanning Trees of Linearly Moving Points. 396-405 - Manuel Blum, Oded Goldreich:
Towards a Computational Theory of Statistical Tests (Extended Abstract). 406-416 - Noga Alon, Zvi Galil, Oded Margalit, Moni Naor:
Witnesses for Boolean Matrix Multiplication and for Shortest Paths. 417-426 - Alfredo De Santis
Zero-Knowledge Proofs of Knowledge Without Interaction (Extended Abstract). 427-436 - Chee-Keng Yap:
Fast Unimodular Reduction: Planar Integer Lattices (Extended Abstract). 437-446 - Johannes Blömer:
How to Denest Ramanujan's Nested Radicals. 447-456 - Wayne Eberly:
On Efficient Band Matrix Arithmetic. 457-463 - Bernd Gärtner:
A Subexponential Algorithm for Abstract Optimization Problems. 464-472 - Noga Alon, Richard A. Duke, Hanno Lefmann, Vojtech Rödl, Raphael Yuster:
The Algorithmic Aspects of the Regularity Lemma (Extended Abstract). 473-481 - László Lovász, Miklós Simonovits:
On the Randomized Complexity of Volume and Diameter. 482-491 - David P. Helmbold, Nick Littlestone, Philip M. Long:
Apple Tasting and Nearly One-Sided Learning. 493-502 - Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan:
Reconstructing Algebraic Functions from Mixed Data. 503-512 - Nader H. Bshouty, Richard Cleve:
On the Exact Learning of Formulas in Parallel (Extended Abstract). 513-522 - Howard Aizenstein, Lisa Hellerstein, Leonard Pitt:
Read-Thrice DNF Is Hard to Learn With Membership and Equivalence Queries. 523-532 - Hisao Tamaki:
Efficient Self-Embedding of Butterfly Networks with Random Faults. 533-541 - Frank Thomson Leighton, Bruce M. Maggs, Ramesh K. Sitaraman
On the Fault Tolerance of Some Popular Bounded-Degree Networks. 542-552 - Uriel Feige, Prabhakar Raghavan:
Exact Analysis of Hot-Potato Routing (Extended Abstract). 553-562 - Sergio A. Felperin, Prabhakar Raghavan, Eli Upfal:
A Theory of Wormhole Routing in Parallel Computers (Extended Abstract). 563-572 - Joseph S. B. Mitchell, Christine D. Piatko
Computing a Shortest k-Link Path in a Polygon. 573-582 - Alok Aggarwal, Amotz Bar-Noy, Samir Khuller, Dina Kravets, Baruch Schieber:
Efficient Minimum Cost Matching Using Quadrangle Inequality. 583-592 - Hubert Wagener:
Optimal Parallel Hull Construction for Simple Polygons in \calO(log log n) Time. 593-599 - Richard Cole, Ramesh Hariharan:
Tighter Bounds on the Exact Complexity of String Matching (Extended Abstract). 600-609 - Claire Kenyon, Richard W. Kenyon:
Tiling a Polygon with Rectangles. 610-619 - Vasek Chvátal, Bruce A. Reed:
Mick Gets Some (the Odds Are on His Side). 620-627 - Torben Hagerup, Rajeev Raman
Waste Makes Haste: Tight Bounds for Loose Parallel Sorting. 628-637 - Shiva Chaudhuri, Jaikumar Radhakrishnan:
The Complexity of Parallel Prefix Problems on Small Domains. 638-647 - Edith Cohen:
Approximate Max Flow on Small Depth Networks. 648-658 - Tomasz Radzik:
Newton's Method for Fractional Combinatorial Optimization. 659-669 - Michele Conforti, Gérard Cornuéjols:
A Class of Logic Problems Solvable by Linear Programming. 670-675 - Sivan Toledo:
Maximizing Non-Linear Concave Functions in Fixed Dimension. 676-685 - Miklós Ajtai, János Komlós, Endre Szemerédi:
Halvers and Expanders. 686-692 - Miklós Ajtai, Noga Alon, Jehoshua Bruck
Fault Tolerant Graphs, Perfect Hash Functions and Disjoint Paths. 693-702 - Victor Y. Pan, John H. Reif, Stephen R. Tate:
The Power of Combining the Techiques of Algebraic and Numerical Computing: Improved Approximate Multipoint Polynomial Evaluation and Improved Multipole Algorithms. 703-713 - Erich L. Kaltofen
Processor-Efficient Parallel Solution of Linear Systems II: The Positive Characteristic and Singular Cases (Extended Abstract). 714-723 - Leonard J. Schulman:
Communication on Noisy Channels: A Coding Theorem for Computation. 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-22 19:32 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: