33. FOCS 1992:
Pittsburgh,
Pennsylvania,
USA
33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, USA, 24-27 October 1992.
IEEE Computer Society 1992
- 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, Endre Szemerédi, Avi Wigderson:
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, Michael E. Saks:
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, Torsten Suel:
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 Kahale:
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, Dirk Van Gucht, Marc Andries, Marc Gyssens:
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, Kazuo Iwano:
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, Giuseppe Persiano:
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, Esther M. Arkin:
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 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, Robert Cypher, Ching-Tien Ho, Moni Naor, Endre Szemerédi:
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 Kaltofen, Victor Y. Pan:
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
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