39. FOCS 1998: Palo Alto, California, USA

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, Michael Mitzenmacher:
  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 Gutiérrez:
  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, Michael E. Saks, Jayram S. Thathachar:
  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, Gábor Tardos:
  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, Umesh V. Vazirani, Avi Wigderson:
  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, Ravi Kannan, Santosh Vempala:
  Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations. 370-378
  
• Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha, Serge A. Plotkin:
  Approximating a Finite Metric by a Small Number of Tree Metrics. 379-388
  
• Santosh 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, Paul E. Kearney, Ming Li:
  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, Balaji Raghavachari:
  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, Ramamohan Paturi, Francis Zane:
  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, Alistair Sinclair, Rolf Wanka:
  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, Avi Wigderson:
  Randomness vs. Time: De-Randomization under a Uniform Assumption. 734-743
  

Last update Wed May 22 23:33:00 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page