Proceedings, 39th Annual Symposium on Foundations of Computer Science. November 8-11, 1998, Palo Alto, California / sponsored by IEEE Computer Society Technical Committee on Mathematical Foundations of Computing.

Format:

Book

Conference/Event

Contributor:

IEEE Xplore (Online service)

IEEE Computer Society. Technical Committee on Mathematical Foundations of Computing.

Conference Name:

Symposium on Foundations of Computer Science (39th : 1998 : Palo Alto, Calif.)

Language:

English

Subjects (All):

Electronic data processing--Congresses.

Electronic data processing.

Machine theory--Congresses.

Machine theory.

Genre:

Conference papers and proceedings.

Physical Description:

xiv, 745 pages : illustrations

Other Title:

39th Annual Symposium on Foundations of Computer Science

Thirty-ninth Annual Symposium on Foundations of Computer Science

Also known as: FOCS '98

Foundations of Computer Science, 1998, proceedings, 39th Annual Symposium on.

Place of Publication:

Los Alamitos, Calif. : IEEE Computer Society Press, [1998]

System Details:

Mode of access: World Wide Web.

text file

Contents:

Geometric Computation and the Art of Sampling / J. Matousek 2

Theoretical Issues in Probabilistic Artificial Intelligence / M. Kearns 4

Information Retrieval on the Web / A. Broder, M.R. Henzinger 6

A Tight Characterization of NP with 3 Query PCPs / V. Guruswami, D. Lewin, M. Sudan, L. Trevisan 8

Probabilistically Checkable Proofs with Low Amortized Query Complexity / M. Sudan, L. Trevisan 18

Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes / V. Guruswami, M. Sudan 28

The Access Network Design Problem / M. Andrews, L. Zhang 40

Jitter Control in QoS Networks / Y. Mansour, B. Patt-Shamir 50

Stability of Adversarial Queues via Fluid Models / D. Gamarnik 60

Delayed Information and Action in On-line Algorithms / S. Albers, M. Charikar, M. Mitzenmacher 71

The Complexity of the Approximation of the Bandwidth Problem / W. Unger 82

The Shortest Vector in a Lattice is Hard to Approximate to Within Some Constant / D. Micciancio 92

Approximating-CVP to Within Almost-Polynomial Factors is NP-Hard / I. Dinur, G. Kindler, S. Safra 99

Satisfiability of Word Equations with Constants is in Exponential Space / C. Gutierrez 112

Decidability of Bisimulation Equivalence for Equational Graphs of Finite Out-Degree / G. Senizergues 120

A Primitive Recursive Algorithm for the General Petri Net Reachability Problem / Z. Bouziane 130

Algorithms to Tile the Infinite Grid with Finite Clusters / M. Szegedy 137

On Approximate Nearest Neighbors in Non-Euclidean Spaces / P. Indyk 148

Pattern Matching for Spatial Point Sets / D.E. Cardoze, L.J. Schulman 156

Faster Algorithms for String Matching Problems: Matching the Convolution Bound / P. Indyk 166

Overcoming the Memory Bottleneck in Suffix Tree Construction / M. Farach, P. Ferragina, S. Muthukrishnan 174

Bivariate Polynomial Multiplication / M. Blaser 186

A Unified Superfast Algorithm for Boundary Rational Tangential Interpolation Problems and for Inversion and Factorization of Dense Structured Matrices / V. Olshevsky, V. Pan 192

Unsatisfiable Systems of Equations, Over a Finite Field / A.R. Woods 202

Multiplicative Complexity of Taylor Shifts and a New Twist of the Substitution Method / A. Schonhage 212

Local Search in Smooth Convex Sets / R. Kannan, A. Nolte 218

A TDI System and its Application to Approximation Algorithms / M.-c. Cai, X. Deng, W. Zang 227

Geometric Separator Theorems & Applications / W.D. Smith, N.C. Wormald 232

Approximation of Diameters: Randomization Doesn't Help / A. Brieden, P. Gritzmann, R. Kannan, V. Klee, L. Lovasz, M. Simonovits 244

Time-Space Tradeoffs for Branching Programs / P. Beame, M. Saks, J.S. Thathachar 254

Optimal Time-Space Trade-Offs for Sorting / J. Pagter, T. Rauhe 264

Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions Over Finite Fields / D. Grigoriev, A.A. Razborov 269

Lower Bounds for (MOD p-MOD m) Circuits / V. Grolmusz, G. Tardos 279

On the Single-Source Unsplittable Flow Problem / Y. Dinitz, N. Garg, M.X. Goemans 290

Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems / N. Garg, J. Konemann 300

All Pairs Shortest Paths in Weighted Directed Graphs

Exact and Almost Exact Algorithms / U. Zwick 310

A Divide-and-Conquer Algorithm for Min-Cost Perfect Matching in the Plane / K.R. Varadarajan 320

1-Way Quantum Finite Automata: Strengths, Weaknesses and Generalizations / A. Ambainis, R. Freivalds 332

The Quantum Communication Complexity of Sampling / A. Ambainis, L.J. Schulman, A. Ta-Shma, U. Vazirani, A. Wigderson 342

Quantum Lower Bounds by Polynomials / R. Beals, H. Buhrman, R. Cleve, M. Mosca, R. de Wolf 352

Quantum Oracle Interrogation: Getting All Information for Almost Half the Price / W. van Dam 362

Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations / A. Frieze, R. Kannan, S. Vempala 370

Approximating a Finite Metric by a Small Number of Tree Metrics / M. Charikar, C. Chekuri, A. Goel, S. Guha, S Plotkin 379

Random Projection: A New Approach to VLSI Layout / S. Vempala 389

Map Graphs in Polynomial Time / M. Thorup 396

On Learning Monotone Boolean Functions / A. Blum, C. Burch, J. Langford 408

Orchestrating Quartets: Approximation and Data Correction / T. Jiang, P. Kearney, M. Li 416

Testing Monotonicity / O. Goldreich, S. Goldwasser, E. Lehman, D. Ron 426

Evolutionary Trees can be Learned in Polynomial Time in the Two-State General Markov Model / M. Cryan, L.A. Goldberg, P.W. Goldberg 436

A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem / K. Jain 448

The Finite Capacity Dial-A-Ride Problem / M. Charikar, B. Raghavachari 458

A Randomized Approximation Scheme for Metric MAX-CUT / W.F. de la Vega, C. Kenyon 468

Semidefinite Relaxations for Parallel Machine Scheduling / M. Skutella 472

Lower Bounds for Zero Knowledge on the Internet / J. Kilian, E. Petrank, C. Rackoff 484

Oblivious Transfer with a Memory-Bounded Receiver / C. Cachin, C. Crepeau, J. Marcil 493

Quantum Cryptography with Imperfect Apparatus / D. Mayers, A. Yao 503

The Security of Individual RSA Bits / J. Hastad, M. Naslund 510

Protocols for Asymmetric Communication Channels / M. Adler, B.M. Maggs 522

Marked Ancestor Problems / S. Alstrup, T. Husfeldt, T. Rauhe 534

Towards an Optimal Bit-Reversal Permutation Program / L. Carter, K.S. Gatlin 544

The Minimum Equivalent DNF Problem and Shortest Implicants / C. Umans 556

Concurrent Reachability Games / L. de Alfaro, T.A. Henzinger, O. Kupferman 564

Perfect Information Leader Election in log* n + O (1) Rounds / A. Russell, D. Zuckerman 576

Random Sampling, Halfspace Range Reporting, and Construction of ([less than or equal] k)-Levels in Three Dimensions / T.M. Chan 586

Parametric and Kinetic Minimum Spanning Trees / P.K. Agarwal, D. Eppstein, L.J. Guibas, M.R. Henzinger 596

On the Combinatorial and Topological Complexity of a Single Cell / S. Basu 606

Which Crossing Number is it, Anyway? / J. Pach, G. Toth 617

An Improved Exponential-Time Algorithm for k-SAT / R. Paturi, P. Pudlak, M.E. Saks, F. Zane 628

Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems / M.L. Bonet, J.L. Esteban, N. Galesi, J. Johannsen 638

Tseitin's Tautologies and Lower Bounds for Nullstellensatz Proofs / D. Grigoriev 648

Which Problems Have Strongly Exponential Complexity? / R. Impagliazzo, R. Paturi, F. Zane 653

Recommendation Systems: A Probabilistic Analysis / R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins 664

Heuristics for Finding Large Independent Sets, with Applications to Coloring Semi-Random Graphs / U. Feige, J. Kilian 674

Improved Bounds and Algorithms for Hypergraph Two-Coloring / J. Radhakrishnan, A. Srinivasan 684

Local Divergence of Markov Chains and the Analysis of Iterative Load-Balancing Schemes / Y. Rabani, A. Sinclair, R. Wanka 694

The Complexity of Acyclic Conjunctive Queries / G. Gottlob, N. Leone, F. Scarcello 706

A Characterization of NC by Tree Recurrence / D. Leivant 716

A Linguistic Characterization of Bounded Oracle Computation and Probabilistic Polynomial Time / J. Mitchell, M. Mitchell, A. Scedrov 725

Randomness vs. Time: De-Randomization under a Uniform Assumption / R. Impagliazzo, A. Wigderson 734.

Notes:

"IEEE Catalog Number 98CB36280"--T.p. verso.

"IEEE Computer Society Press Order Number PR9172"--T.p. verso.

Includes bibliographical references and author index.

ISBN:

0818691727

9780818691720

0780352297

9780780352292

0818691743

9780818691744

OCLC:

40434496

Access Restriction:

Restricted for use by site license.