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