default search action
39th FOCS 1998: Palo Alto, California, USA
- 39th Annual Symposium on Foundations of Computer Science, FOCS '98, November 8-11, 1998, Palo Alto, California, USA. IEEE Computer Society 1998, ISBN 0-8186-9172-7
Tutorial I
- Jirí Matousek:
Geometric Computation and the Art of Sampling. 2
Tutorial II
- Michael J. Kearns:
Theoretical Issues in Probabilistic Artificial Intelligence. 4
Tutorial III
- Andrei Z. Broder, Monika Rauch Henzinger:
Information Retrieval on the Web. 6
Session 1A
- Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan:
A Tight Characterization of NP with 3 Query PCPs. 8-17 - Madhu Sudan, Luca Trevisan
:
Probabilistically Checkable Proofs with Low Amortized Query Complexity. 18-27 - Venkatesan Guruswami, Madhu Sudan:
Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes. 28-39
Session 1B
- Matthew Andrews, Lisa Zhang:
The Access Network Design Problem. 40-59 - Yishay Mansour, Boaz Patt-Shamir:
Jitter Control in QoS Networks. 50-59 - David Gamarnik:
Stability of Adversarial Queues via Fluid Models. 60-70 - Susanne Albers, Moses Charikar
Delayed Information and Action in On-line Algorithms. 71-81
Session 2A
- Walter Unger:
The Complexity of the Approximation of the Bandwidth Problem. 82-91 - Daniele Micciancio:
The Shortest Vector in a Lattice is Hard to Approximate to Within Some Constant. 92-98 - Irit Dinur, Guy Kindler, Shmuel Safra
Approximating-CVP to Within Almost-Polynomial Factors is NP-Hard. 99-111
Session 2B
- Claudio Gutierrez:
Satisfiability of Word Equations with Constants is in Exponential Space. 112-119 - Géraud Sénizergues:
Decidability of Bisimulation Equivalence for Equational Graphs of Finite Out-Degree. 120-129 - Zakaria Bouziane:
A Primitive Recursive Algorithm for the General Petri Net Reachability Problem. 130-136 - Mario Szegedy:
Algorithms to Tile the Infinite Grid with Finite Clusters. 137-147
Session 3A
- Piotr Indyk:
On Approximate Nearest Neighbors in Non-Euclidean Spaces. 148-155 - David E. Cardoze, Leonard J. Schulman:
Pattern Matching for Spatial Point Sets. 156-165 - Piotr Indyk:
Faster Algorithms for String Matching Problems: Matching the Convolution Bound. 166-173 - Martin Farach, Paolo Ferragina, S. Muthukrishnan:
Overcoming the Memory Bottleneck in Suffix Tree Construction. 174-185
Session 3B
- Markus Bläser:
Bivariate Polynomial Multiplication. 186-191 - Vadim Olshevsky, Victor Y. Pan:
A Unified Superfast Algorithm for Boundary Rational Tangential Interpolation Problems and for Inversion and Factorization of Dense Structured Matrices. 192-201 - Alan R. Woods:
Unsatisfiable Systems of Equations, Over a Finite Field. 202-211 - Arnold Schönhage:
Multiplicative Complexity of Taylor Shifts and a New Twist of the Substitution Method. 212-217
Session 4A
- Ravi Kannan, Andreas Nolte:
Local Search in Smooth Convex Sets. 218-226 - Mao-cheng Cai, Xiaotie Deng, Wenan Zang:
A TDI System and its Application to Approximation Algorithms. 227-243 - Warren D. Smith, Nicholas C. Wormald:
Geometric Separator Theorems & Applications. 232-243 - Andreas Brieden, Peter Gritzmann, Ravi Kannan, Victor Klee, László Lovász, Miklós Simonovits:
Approximation of Diameters: Randomization Doesn't Help. 244-251
Session 4B
- Paul Beame
Time-Space Tradeoffs for Branching Programs. 254-263 - Jakob Pagter, Theis Rauhe:
Optimal Time-Space Trade-Offs for Sorting. 264-268 - Dima Grigoriev, Alexander A. Razborov:
Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions Over Finite Fields. 269-278 - Vince Grolmusz
Lower Bounds for (MOD p - MOD m) Circuits. 279-289
Session 5A
- Yefim Dinitz, Naveen Garg, Michel X. Goemans:
On the Single-Source Unsplittable Flow Problem. 290-299 - Naveen Garg, Jochen Könemann:
Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems. 300-309 - Uri Zwick:
All Pairs Shortest Paths in Weighted Directed Graphs ¾ Exact and Almost Exact Algorithms. 310-319 - Kasturi R. Varadarajan:
A Divide-and-Conquer Algorithm for Min-Cost Perfect Matching in the Plane. 320-331
Session 5B
- Andris Ambainis, Rusins Freivalds:
1-Way Quantum Finite Automata: Strengths, Weaknesses and Generalizations. 332-341 - Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma
The Quantum Communication Complexity of Sampling. 342-351 - Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald de Wolf:
Quantum Lower Bounds by Polynomials. 352-361 - Wim van Dam:
Quantum Oracle Interrogation: Getting All Information for Almost Half the Price. 362-367
Session 6A
- Alan M. Frieze
Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations. 370-378 - Moses Charikar
Approximating a Finite Metric by a Small Number of Tree Metrics. 379-388 - Santosh S. Vempala:
Random Projection: A New Approach to VLSI Layout. 389-395 - Mikkel Thorup:
Map Graphs in Polynomial Time. 396-405
Session 6B
- Avrim Blum, Carl Burch, John Langford:
On Learning Monotone Boolean Functions. 408-415 - Tao Jiang
Orchestrating Quartets: Approximation and Data Correction. 416-425 - Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron:
Testing Monotonicity. 426-435 - Mary Cryan, Leslie Ann Goldberg, Paul W. Goldberg
Evolutionary Trees can be Learned in Polynomial Time in the Two-State General Markov Model. 436-445
Session 7A
- Kamal Jain:
Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem. 448-457 - Moses Charikar
The Finite Capacity Dial-A-Ride Problem. 458-467 - Wenceslas Fernandez de la Vega, Claire Kenyon:
A Randomized Approximation Scheme for Metric MAX-CUT. 468-471 - Martin Skutella:
Semidefinite Relaxations for Parallel Machine Scheduling. 472-481
Session 7B
- Joe Kilian, Erez Petrank, Charles Rackoff:
Lower Bounds for Zero Knowledge on the Internet. 484-492 - Christian Cachin, Claude Crépeau, Julien Marcil:
Oblivious Transfer with a Memory-Bounded Receiver. 493-502 - Dominic Mayers, Andrew Chi-Chih Yao:
Quantum Cryptography with Imperfect Apparatus. 503-509 - Johan Håstad, Mats Näslund:
The Security of Individual RSA Bits. 510-521
Session 8A
- Micah Adler, Bruce M. Maggs:
Protocols for Asymmetric Communication Channels. 522-533 - Stephen Alstrup, Thore Husfeldt, Theis Rauhe:
Marked Ancestor Problems. 534-544 - Larry Carter, Kang Su Gatlin:
Towards an Optimal Bit-Reversal Permutation Program. 544-555
Session 8B
- Christopher Umans:
The Minimum Equivalent DNF Problem and Shortest Implicants. 556-563 - Luca de Alfaro, Thomas A. Henzinger, Orna Kupferman:
Concurrent Reachability Games. 564-575 - Alexander Russell, David Zuckerman:
Perfect Information Leader Election in log*n + O(1) Rounds. 576-583
Session 9A
- Timothy M. Chan:
Sampling, Halfspace Range Reporting, and Construction of (<= k)-Levels in Three Dimensions. 586-595 - Pankaj K. Agarwal, David Eppstein, Leonidas J. Guibas, Monika Rauch Henzinger:
Parametric and Kinetic Minimum Spanning Trees. 596-605 - Saugata Basu:
On the Combinatorial and Topological Complexity of a Single Cell. 606-616 - János Pach, Géza Tóth:
Which Crossing Number is it, Anyway? 617-627
Session 9B
- Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane:
An Improved Exponential-Time Algorithm for k-SAT. 628-637 - Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, Jan Johannsen:
Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems. 638-647 - Dima Grigoriev:
Tseitin's Tautologies and Lower Bounds for Nullstellensatz Proofs. 648-652 - Russell Impagliazzo
Which Problems Have Strongly Exponential Complexity? 653-663
Session 10A
- Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins:
Recommendation Systems: A Probabilistic Analysis. 664-673 - Uriel Feige, Joe Kilian:
Heuristics for Finding Large Independent Sets, with Applications to Coloring Semi-Random Graphs. 674-683 - Jaikumar Radhakrishnan, Aravind Srinivasan:
Improved Bounds and Algorithms for Hypergraph Two-Coloring. 684-693 - Yuval Rabani
Local Divergence of Markov Chains and the Analysis of Iterative Load Balancing Schemes. 694-705
Session 10B
- Georg Gottlob, Nicola Leone, Francesco Scarcello:
The Complexity of Acyclic Conjunctive Queries. 706-715 - Daniel Leivant:
A Characterization of NC by Tree Recurrence. 716-724 - John C. Mitchell, Mark Mitchell, Andre Scedrov:
A Linguistic Characterization of Bounded Oracle Computation and Probabilistic Polynomial Time. 725-733 - Russell Impagliazzo
Randomness vs. Time: De-Randomization under a Uniform Assumption. 734-743
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:50 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: