Default Cover Image

Proceedings of 37th Conference on Foundations of Computer Science

Oct. 14 1996 to Oct. 16 1996

Burlington, VT

ISBN: 0-8186-7594-2

Table of Contents

ForewordFreely available from IEEE.pp. x
CommitteesFreely available from IEEE.pp. xi
ReviewersFreely available from IEEE.pp. xii
Session 1A, Chair: Rajeev Motwani
Polynomial time approximation schemes for Euclidean TSP and other geometric problemsFull-text access may be available. Sign in or learn about subscription options.pp. 2
Session 1A, Chair: Rajeev Motwani
The regularity lemma and approximation schemes for dense problemsFull-text access may be available. Sign in or learn about subscription options.pp. 12
Session 1A, Chair: Rajeev Motwani
A new rounding procedure for the assignment problem with applications to dense graph arrangement problemsFull-text access may be available. Sign in or learn about subscription options.pp. 21
Session 1A, Chair: Rajeev Motwani
Approximate strip packingFull-text access may be available. Sign in or learn about subscription options.pp. 31
Session 1B, Chair: Russell Impagliazzo
A decision procedure for unitary linear quantum cellular automataFull-text access may be available. Sign in or learn about subscription options.pp. 38
Session 1B, Chair: Russell Impagliazzo
Polynomial simulations of decohered quantum computersFull-text access may be available. Sign in or learn about subscription options.pp. 46
Session 1B, Chair: Russell Impagliazzo
Fault-tolerant quantum computationFull-text access may be available. Sign in or learn about subscription options.pp. 56
Session 2A, Chair: David Karger
Single-source unsplittable flowFull-text access may be available. Sign in or learn about subscription options.pp. 68
Session 2A, Chair: David Karger
The optimal path-matching problemFull-text access may be available. Sign in or learn about subscription options.pp. 78
Session 2A, Chair: David Karger
Short paths in expander graphsFull-text access may be available. Sign in or learn about subscription options.pp. 86
Session 2A, Chair: David Karger
Spectral partitioning works: planar graphs and finite element meshesFull-text access may be available. Sign in or learn about subscription options.pp. 96-105
Session 2B, Chair: Chee Yap
Computing permanents over fields of characteristic 3: where and why it becomes difficultFull-text access may be available. Sign in or learn about subscription options.pp. 108
Session 2B, Chair: Chee Yap
Solving systems of polynomial congruences modulo a large primeFull-text access may be available. Sign in or learn about subscription options.pp. 115
Session 2B, Chair: Chee Yap
Median Selection Requires ComparisonsFull-text access may be available. Sign in or learn about subscription options.pp. 125
Session 2B, Chair: Chee Yap
Faster deterministic sorting and searching in linear spaceFull-text access may be available. Sign in or learn about subscription options.pp. 135
Session 3A, Chair: Baruch Schieber
An efficient algorithm for constructing minimal trellises for codes over finite Abelian groupsFull-text access may be available. Sign in or learn about subscription options.pp. 144
Session 3A, Chair: Baruch Schieber
Highly fault-tolerant parallel computationFull-text access may be available. Sign in or learn about subscription options.pp. 154
Session 3A, Chair: Baruch Schieber
Maximum likelihood decoding of Reed Solomon codesFull-text access may be available. Sign in or learn about subscription options.pp. 164
Session 3A, Chair: Baruch Schieber
New coding techniques for improved bandwidth utilizationFull-text access may be available. Sign in or learn about subscription options.pp. 173
Session 3B, Chair: Sandy Irani
Probabilistic approximation of metric spaces and its algorithmic applicationsFull-text access may be available. Sign in or learn about subscription options.pp. 184
Session 3B, Chair: Sandy Irani
Factoring graphs to bound mixing ratesFull-text access may be available. Sign in or learn about subscription options.pp. 194
Session 3B, Chair: Sandy Irani
Sampling according to the multivariate normal densityFull-text access may be available. Sign in or learn about subscription options.pp. 204
Session 3B, Chair: Sandy Irani
Load balancing and density dependent jump Markov processesFull-text access may be available. Sign in or learn about subscription options.pp. 213
Session 4A, Chair: Tandy Warnow
Tree data structures for N-body simulationFull-text access may be available. Sign in or learn about subscription options.pp. 224
Session 4A, Chair: Tandy Warnow
Efficient information gathering on the InternetFull-text access may be available. Sign in or learn about subscription options.pp. 234
Session 4A, Chair: Tandy Warnow
Approximate option pricingFull-text access may be available. Sign in or learn about subscription options.pp. 244
Session 4B, Chair: Dexter Kozen
Temporal logic and semidirect products: an effective characterization of the until hierarchyFull-text access may be available. Sign in or learn about subscription options.pp. 256
Session 4B, Chair: Dexter Kozen
Equivalence in finite-variable logics is complete for polynomial timeFull-text access may be available. Sign in or learn about subscription options.pp. 264
Session 4B, Chair: Dexter Kozen
Simplified and improved resolution lower boundsFull-text access may be available. Sign in or learn about subscription options.pp. 274
Session 5, Chair: Martin Tompa
Computationally hard algebraic problemsFull-text access may be available. Sign in or learn about subscription options.pp. 284
Session 6A, Chair: Tandy Warnow
Approximating minimum-size k-connected spanning subgraphs via matchingFull-text access may be available. Sign in or learn about subscription options.pp. 292
Session 6A, Chair: Tandy Warnow
A 3-approximation for the minimum tree spanning k verticesFull-text access may be available. Sign in or learn about subscription options.pp. 302
Session 6A, Chair: Tandy Warnow
An 8-approximation algorithm for the subset feedback vertex set problemFull-text access may be available. Sign in or learn about subscription options.pp. 310
Session 6A, Chair: Tandy Warnow
Efficient approximate and dynamic matching of patterns using a labeling paradigmFull-text access may be available. Sign in or learn about subscription options.pp. 320
Session 6B, Chair: Russell Impagliazzo
A polynomial-time algorithm for learning noisy linear threshold functionsFull-text access may be available. Sign in or learn about subscription options.pp. 330
Session 6B, Chair: Russell Impagliazzo
Property testing and its connection to learning and approximationFull-text access may be available. Sign in or learn about subscription options.pp. 339
Session 6B, Chair: Russell Impagliazzo
On the applications of multiplicity automata in learningFull-text access may be available. Sign in or learn about subscription options.pp. 349
Session 6B, Chair: Russell Impagliazzo
Learning linear transformationsFull-text access may be available. Sign in or learn about subscription options.pp. 359
Session 7A, Chair: S. Rao Kosaraju
Deterministic routing with bounded buffers: turning offline into online protocolsFull-text access may be available. Sign in or learn about subscription options.pp. 370
Session 7A, Chair: S. Rao Kosaraju
Universal stability results for greedy contention-resolution protocolsFull-text access may be available. Sign in or learn about subscription options.pp. 380
Session 7A, Chair: S. Rao Kosaraju
A general approach to dynamic packet routing with bounded buffersFull-text access may be available. Sign in or learn about subscription options.pp. 390
Session 7A, Chair: S. Rao Kosaraju
Path coloring on the meshFull-text access may be available. Sign in or learn about subscription options.pp. 400
Session 7B, Chair: Anne Condon
Discrepancy sets and pseudorandom generators for combinatorial rectanglesFull-text access may be available. Sign in or learn about subscription options.pp. 412
Session 7B, Chair: Anne Condon
The Boolean isomorphism problemFull-text access may be available. Sign in or learn about subscription options.pp. 422
Session 7B, Chair: Anne Condon
Potential of the approximation methodFull-text access may be available. Sign in or learn about subscription options.pp. 431
Session 7B, Chair: Anne Condon
Static Dictionaries on RAMs: Query Time is Necessary and SufficientFull-text access may be available. Sign in or learn about subscription options.pp. 441
Session 8A, Chair: Chee Yap
All pairs almost shortest pathsFull-text access may be available. Sign in or learn about subscription options.pp. 452
Session 8A, Chair: Chee Yap
Computing vertex connectivity: new bounds from old techniquesFull-text access may be available. Sign in or learn about subscription options.pp. 462
Session 8A, Chair: Chee Yap
New lower bounds for halfspace emptinessFull-text access may be available. Sign in or learn about subscription options.pp. 472
Session 8A, Chair: Chee Yap
Binary space partitions for fat rectanglesFull-text access may be available. Sign in or learn about subscription options.pp. 482
Session 8B, Chair: Carsten Lund
On the knowledge complexity of N PFull-text access may be available. Sign in or learn about subscription options.pp. 494
Session 8B, Chair: Carsten Lund
Incoercible multiparty computationFull-text access may be available. Sign in or learn about subscription options.pp. 504
Session 8B, Chair: Carsten Lund
Pseudorandom functions revisited: the cascade construction and its concrete securityFull-text access may be available. Sign in or learn about subscription options.pp. 514
Session 8B, Chair: Carsten Lund
The geometry of coin-weighing problemsFull-text access may be available. Sign in or learn about subscription options.pp. 524
Session 9, Chair: Rajeev Motwani
Universal data compression and portfolio selectionFull-text access may be available. Sign in or learn about subscription options.pp. 534
Session 10A, Chair: Sandy Irani
Near-optimal parallel prefetching and cachingFull-text access may be available. Sign in or learn about subscription options.pp. 540
Session 10A, Chair: Sandy Irani
New algorithms for the disk scheduling problemFull-text access may be available. Sign in or learn about subscription options.pp. 550
Session 10A, Chair: Sandy Irani
Optimal dynamic interval management in external memoryFull-text access may be available. Sign in or learn about subscription options.pp. 560
Session 10A, Chair: Sandy Irani
Fast fault-tolerant concurrent access to shared objectsFull-text access may be available. Sign in or learn about subscription options.pp. 570
Session 10A, Chair: Sandy Irani
Fault tolerant data structuresFull-text access may be available. Sign in or learn about subscription options.pp. 580
Session 10B, Chair: Michael Luby
Approximate checking of polynomials and functional equationsFull-text access may be available. Sign in or learn about subscription options.pp. 592
Session 10B, Chair: Michael Luby
Efficient self-testing/self-correction of linear recurrencesFull-text access may be available. Sign in or learn about subscription options.pp. 602
Session 10B, Chair: Michael Luby
Verifying identitiesFull-text access may be available. Sign in or learn about subscription options.pp. 612
Session 10B, Chair: Michael Luby
Gadgets Approximation, and Linear ProgrammingFull-text access may be available. Sign in or learn about subscription options.pp. 617
Session 10B, Chair: Michael Luby
Clique is hard to approximate within n1-εFull-text access may be available. Sign in or learn about subscription options.pp. 627
Session 10B, Chair: Michael Luby
Author IndexFreely available from IEEE.pp. 637
Showing 70 out of 70