close
1.

図書

図書
sponsored by IEEE Computer Society Technical Committee on Mathematical Foundations of Computing
出版情報: Los Alamitos, Calif. ; Tokyo : IEEE Computer Society, c2001  xiii, 670 p. ; 28 cm
所蔵情報: loading…
2.

図書

図書
sponsored by IEEE Computer Society Technical Committee on Mathematical Foundations of Computing
出版情報: Los Alamitos, Calif. ; Tokyo : IEEE Computer Society, c2005  xiii, 668 p. ; 28 cm
所蔵情報: loading…
3.

図書

図書
sponsored by IEEE Computer Society Technical Society on Foundations of Computing
出版情報: Los Alamitos, Calif. ; Tokyo : IEEE Computer Society, c2004  xiv, 632 p. ; 28 cm
所蔵情報: loading…
目次情報: 続きを見る
Foreword
Conference Organization and Program Committee
Reviewers
Quantum Weak Coin-Flipping with Bias of 0.192 / C. MochonSession 1:
Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs / H. Klauck ; R. Spalek ; R. de Wolf
Quantum Walk Algorithm for Element Distinctness / A. Ambainis
Quantum Speed-Up of Markov Chain Based Algorithms / M. Szegedy
Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation / D. Aharonov ; W. van Dam ; J. Kempe ; Z. Landau ; S. Lloyd ; O. Regev
Maximizing Quadratic Programs: Extending Grothendieck's Inequality / M. Charikar ; A. WirthSession 2:
An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem / L. Lau
Edge-Disjoint Paths in Planar Graphs / C. Chekuri ; S. Khanna ; F. Shepherd
Machine Minimization for Scheduling Jobs with Interval Constraints / J. Chuzhoy ; S. Guha ; J. Naor
Random Edge Can Be Exponential on Abstract Cubes / J. Matousek ; T. SzaboSession 3:
On the Integrality Ratio for Asymmetric TSP / M. Goemans ; H. Karloff
The Hardness of Metric Labeling
Hardness of Buy-at-Bulk Network Design / M. Andrews
Hardness of Approximating the Shortest Vector Problem in Lattices / S. KhotSession 4:
Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique
Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs? / G. Kindler ; E. Mossel ; R. O'Donnell
Assignment Testers: Towards a Combinatorial Proof of the PCP-Theorem / I. Dinur ; O. Reingold
Cryptography in NC[superscript 0] / B. Applebaum ; Y. Ishai ; E. KushilevitzSession 5:
An Unconditional Study of Computational Zero Knowledge / S. Vadhan
Universally Composable Protocols with Relaxed Set-Up Assumptions / B. Barak ; R. Canetti ; J. Nielsen ; R. Pass
On the (Im)possibility of Cryptography with Imperfect Randomness / Y. Dodis ; S. Ong ; M. Prabhakaran ; A. Sahai
Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity / B. Dean ; J. VondrakSession 6:
An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design / A. Gupta ; R. Ravi ; A. Sinha
Stochastic Optimization is (Almost) as easy as Deterministic Optimization / D. Shmoys ; C. Swamy
O([radical]log n) Approximation to SPARSEST CUT in O(n[superscript 2]) Time / S. Arora ; E. Hazan ; S. Kale
Maximum Matchings via Gaussian Elimination / M. Mucha ; P. Sankowski
Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game / R. Savani ; B. von StengelSession 7:
Edge Pricing of Multicommodity Networks for Heterogeneous Selfish Users / G. Karakostas ; S. Kolliopoulos
Tolls for Heterogeneous Selfish Users in Multicommodity Networks and Generalized Congestion Games / L. Fleischer ; K. Jain ; M. Mahdian
A Polynomial Time Algorithm for Computing the Arrow-Debreu Market Equilibrium for Linear Utilities
The Price of Stability for Network Design with Fair Cost Allocation / E. Anshelevich ; A. Dasgupta ; J. Kleinberg ; E. Tardos ; T. Wexler ; T. Roughgarden
Holographic Algorithms (Extende Abstract) / L. ValiantSession 8:
Hierarchy Theorems for Probabilistic Polynomial Time / L. Fortnow ; R. Santhanam
Private Codes or Succinct Random Codes That Are (Almost) Perfect / M. Langberg
On the List and Bounded Distance Decodibility of the Reed-Solomon Codes (Extended Abstract) / Q. Cheng ; D. Wan
Multilinear-NC[subscript 1 not equal]Multilinear-NC[subscript 2] / R. RazSession 9:
Algebras with Polynomial Identities and Computing the Determinant / S. Chien ; A. Sinclair
Lattice Problems in NP [intersection of]coNP
Worst-Case to Average-Case Reductions Based on Gaussian Measures / D. Micciancio
Extracting Randomness Using Few Independent Sources / R. Impagliazzo ; A. WigdersonSession 10:
Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed / A. Gabizon ; R. Shaltiel
Constructing Expander Graphs by 2-Lifts and Discrepancy vs. Spectral Gap / Y. Bilu ; N. Linial
Testing Polynomials over General Fields / T. Kaufman ; D. Ron
Testing Low-Degree Polynomials over Prime Fields / C. Jutla ; A. Patthak ; A. Rudra ; D. Zuckerman
Measured Descent: A New Embedding Method for Finite Metrics / R. Krauthgamer ; J. Lee ; M. Mendel ; A. NaorSession 11:
Triangulation and Embedding Using Small Sets of Beacons / A. Slivkins
A Simple Linear Time (1 + [varepsilon])-Approximation Algorithm for k-Means Clustering in Any Dimensions / A. Kumar ; Y. Sabharwal ; S. Sen
On the Power of Discrete and of Lexicographic Helly-Type Theorems / N. Halman
An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching / A. Chakrabarti
Dynamic Optimality--Almost / E. Demaine ; D. Harmon ; J. Iacono ; M. PatrascuSession 12:
No Sorting? Better Searching! / G. Franceschini ; R. Grossi
Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs / L. Roditty ; U. Zwick
Dynamic Transitive Closure via Dynamic Matrix Inverse (Extended Abstract)
Dynamic Speed Scaling to Manage Energy and Temperature / N. Bansal ; T. Kimbrel ; K. PruhsSession 13:
Optimal Power-Down Strategies / J. Augustine ; S. Irani
On the Streaming Model Augmented with a Sorting Primitive / G. Aggarwal ; M. Datar ; S. Rajagopalan ; M. Ruhl
Approximating Edit Distance Efficiently / Z. Bar-Yossef ; T. Jayram ; R. Kumar
Strong Spatial Mixing for Lattice Graphs with Fewer Colours / L. Goldberg ; R. Martin ; M. PatersonSession 14:
Shuffling by Semi-Random Transpositions / Y. Peres
Randomly Coloring Constant Degree Graphs / M. Dyer ; A. Frieze ; T. Hayes ; E. Vigoda
The Exact Satisfiability Threshold for a Potentially Intractible Random Constraint Satisfaction Problem / H. Connamacher ; M. Molloy
Spectral Analysis of Random Graphs with Skewed Degree Distributions / J. Hopcroft ; F. McSherrySession 15:
Learning with Errors in Answers to Membership Queries (Extended Abstract) / L. Bisht ; N. Bshouty ; L. Khoury
Learnability and Automatizability / M. Alekhnovich ; M. Braverman ; V. Feldman ; A. Klivans ; T. Pitassi
Author Index
Foreword
Conference Organization and Program Committee
Reviewers
4.

図書

図書
sponsored by IEEE Computer Society Technical Committee on Mathematical Foundations of Computing
出版情報: Los Alamitos, Calif. : IEEE Computer Society Press, c1999  xiv, 668 p. ; 28 cm
所蔵情報: loading…
目次情報: 続きを見る
Foreword
Committees
Machtey Award
Reviewers
Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems / K. Jain ; V. V. Vazirani
Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields / J. Kleinberg ; E. Tardos
Approximating Fractional Multicommodity Flow Independent of the Number of Commodities / L. K. Fleischer
Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates / F. Afrati ; E. Bampis ; C. Chekuri ; D. Karger ; C. Kenyon ; S. Khanna ; I. Milis ; M. Queyranne ; M. Skutella ; C. Stein ; M. Sviridenko
A 5/2n[superscript 2]-Lower Bound for the Rank of nxn-Matrix Multiplication over Arbitrary Fields / M. Blaser
Improved Bounds for Sampling Colorings / E. Vigoda
A Non-linear Time Lower Bound for Boolean Branching Programs / M. Ajtai
Derandomizing Arthur-Merlin Games Using Hitting Sets / P. Bro Miltersen ; N. V. Vinodchandran
Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs / V. King
Knuth Prize Lecture / Laszlo Lovasz
Dynamic Planar Convex Hull Operations in Near-Logarithmic Amortized Time / T. M. Chan
Taking a Walk in a Planar Arrangement / S. Har-Peled
PSPACE Has Constant-round Quantum Interactive Proof Systems / J. Watrous
Verifiable Random Functions / S. Micali ; M. Rabin ; S. Vadhan
How Asymmetry Helps Load Balancing / B. Vocking
Noncryptographic Selection Protocols / U. Feige
A Sublinear Time Approximation Scheme for Clustering in Metric Spaces / P. Indyk
Efficient Regular Data Structures and Algorithms for Location and Proximity Problems / A. Amir ; A. Efrat ; H. Samet
Approximate Nearest Neighbor Algorithms for Hausdorff Metrics via Embeddings / M. Farach-Colton
Near-Optimal Conversion of Hardness into Pseudo-Randomness / R. Impagliazzo ; R. Shaltiel ; A. Wigderson
Error Reduction for Extractors / R. Raz ; O. Reingold
Primality and Identity Testing Via Chinese Remaindering / M. Agrawal ; S. Biswas
On Counting Independent Sets in Sparse Graphs / M. Dyer ; A. Frieze ; M. Jerrum
Torpid Mixing of Some Monte Carlo Markov Chain Algorithms in Statistical Physics / C. Borgs ; J. Chayes ; J. H. Kim ; P. Tetali ; V. H. Vu
Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions / B. Morris ; A. Sinclair
Markovian Coupling vs. Conductance for the Jerrum-Sinclair Chain / V.S. Anil Kumar ; H. Ramesh
A Near-Tight Lower Bound on the Time Complexity of Distributed MST Construction / D. Peleg ; V. Rubinovich
Long-lived Adaptive Collect with Applications / Y. Afek ; G. Stupp ; D. Touitou
A Theoretical Framework for Memory-Adaptive Algorithms / R. D. Barve ; J. S. Vitter
Cache-Oblivious Algorithms / M. Frigo ; C. E. Leiserson ; H. Prokop ; S. Ramachandran
The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals / J. Feldman ; M. Ruhl
Setting Parameters by Example / D. Eppstein
Finding Double Euler Trails of Planar Graphs in Linear Time / Z.-Z. Chen ; X. He ; C.-H. Huang
Edge-Disjoint Routing in Plane Switch Graphs in Linear Time / K. Weihe
On Quantum and Classical Space-bounded Processes with Algebraic Transition Amplitudes
A Better Lower Bound for Quantum Algorithms Searching an Ordered List / A. Ambainis
Bounds for Small-Error and Zero-Error Quantum Algorithms / H. Buhrman ; R. Cleve ; R. de Wolf ; C. Zalka
Optimal Lower Bounds for Quantum Automata and Random Access Codes / A. Nayak
Improved Combinatorial Algorithms for the Facility Location and k-Median Problems / M. Charikar ; S. Guha
Lovasz's Lemma for the Three-Dimensional K-Level of Concave Surfaces and its Applications / N. Katoh ; T. Tokuyama
Cuts, Trees and l[subscript 1]-Embeddings of Graphs / A. Gupta ; I. Newman ; Y. Rabinovich
A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems / U. Schoning
Random CNF's are Hard for the Polynomial Calculus / E. Ben-Sasson
A Study of Proof Search Algorithms for Resolution and Polynomial Calculus / M. L. Bonet ; N. Galesi
Online Scheduling to Minimize Average Stretch / S. Muthukrishnan ; R. Rajaraman ; A. Shaheen ; J. E. Gehrke
Weak Adversaries for the k-Server Problem / E. Koutsoupias
Finely-Competitive Paging / A. Blum ; C. Burch ; A. Kalai
On the Complexity of SAT / R. J. Lipton ; A. Viglas
Hardness of Approximating [characters not reproducible] Minimization Problems / C. Umans
Hardness of Approximating the Minimum Distance of a Linear Code / I. Dumer ; D. Micciancio ; M. Sudan
On Universal and Fault-Tolerant Quantum Computing: A Novel Basis and a New Constructive Proof of Universality for Shor's Basis / P. O. Boykin ; T. Mor ; M. Pulver ; V. Roychowdhury ; F. Vatan
Satisfiability of Word Equations with Constants is in PSPACE / W. Plandowski
An Approximate L[superscript 1]-Difference Algorithm for Massive Data Streams / J. Feigenbaum ; S. Kannan ; M. Strauss ; M. Viswanathan
Algorithmic Aspects of Protein Structure Similarity / D. Goldman ; S. Istrail ; C. H. Papadimitriou
Magic Functions / C. Dwork ; M. Naor ; L. Stockmeyer
Limits on the Efficiency of One-Way Permutation-Based Hash Functions / D. R. Simon
Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security / A. Sahai
Non-Interactive CryptoComputing For NC[superscript 1] / T. Sander ; A. Young ; M. Yung
Fairness in Routing and Load Balancing / Y. Rabani
Stochastic Load Balancing and Related Problems / A. Goel
Reducing Network Congestion and Blocking Probability Through Balanced Allocation / M. J. Luczak ; E. Upfal
Finding Maximal Repetitions in a Word in Linear Time / R. Kolpakov ; G. Kucherov
All Pairs Shortest Paths in Undirected Graphs with Integer Weights / A. Shoshan ; U. Zwick
An Algorithmic Theory of Learning: Robust Concepts and Random Projection / R. I. Arriaga ; S. Vempala
Boosting and Hard-Core Sets / A. R. Klivans ; R. A. Servedio
Learning Mixtures of Gaussians / S. Dasgupta
Regular Languages Are Testable with a Constant Number of Queries / N. Alon ; M. Krivelevich ; M. Szegedy
Efficient Testing of Large Graphs / E. Fischer
Author Index
Foreword
Committees
Machtey Award
5.

図書

図書
sponsored by IEEE Computer Society, IEEE Computer Society Technical Committee on Mathematical Foundations of Computing
出版情報: Los Alamitos, Calif. : IEEE Computer Society Press, c1997  xiii, 606 p. ; 28 cm
所蔵情報: loading…
6.

図書

図書
sponsored by IEEE Computer Society Technical Committee on Mathematical Foundations of Computing
出版情報: Los Alamitos, Calif. : IEEE Computer Society Press, c1998  xiv, 745 p. ; 28 cm
所蔵情報: loading…
目次情報: 続きを見る
Foreword
Committees
Reviewers
Geometric Computation and the Art of Sampling / Emo Welzl ; J. MatousekTutorial I:
Theoretical Issues in Probabilistic Artificial Intelligence / Sally Goldman ; M. KearnsTutorial II:
Information Retrieval on the Web / David Karger ; A. Broder ; M.R. HenzingerTutorial III:
A Tight Characterization of NP with 3 Query PCPs / Mihir Bellare ; V. Guruswami ; D. Lewin ; M. Sudan ; L. TrevisanSession 1A:
Probabilistically Checkable Proofs with Low Amortized Query Complexity
Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes
The Access Network Design Problem / Jon Kleinberg ; M. Andrews ; L. ZhangSession 1B:
Jitter Control in QoS Networks / Y. Mansour ; B. Patt-Shamir
Stability of Adversarial Queues via Fluid Models / D. Gamarnik
Delayed Information and Action in On-line Algorithms / S. Albers ; M. Charikar ; M. Mitzenmacher
The Complexity of the Approximation of the Bandwidth Problem / Miklos Ajtai ; W. UngerSession 2A:
The Shortest Vector in a Lattice is Hard to Approximate to Within Some Constant / D. Micciancio
Approximating-CVP to Within Almost-Polynomial Factors is NP-Hard / I. Dinur ; G. Kindler ; S. Safra
Satisfiability of Word Equations with Constants is in Exponential Space / Christos Papadimitriou ; C. GutierrezSession 2B:
Decidability of Bisimulation Equivalence for Equational Graphs of Finite Out-Degree / G. Senizergues
A Primitive Recursive Algorithm for the General Petri Net Reachability Problem / Z. Bouziane
Algorithms to Tile the Infinite Grid with Finite Clusters / M. Szegedy
On Approximate Nearest Neighbors in Non-Euclidean Spaces / Frances Yao ; P. IndykSession 3A:
Pattern Matching for Spatial Point Sets / D.E. Cardoze ; L.J. Schulman
Faster Algorithms for String Matching Problems: Matching the Convolution Bound
Overcoming the Memory Bottleneck in Suffix Tree Construction / M. Farach ; P. Ferragina ; S. Muthukrishnan
Bivariate Polynomial Multiplication / Dan Spielman ; M. BlaserSession 3B:
A Unified Superfast Algorithm for Boundary Rational Tangential Interpolation Problems and for Inversion and Factorization of Dense Structured Matrices / V. Olshevsky ; V. Pan
Unsatisfiable Systems of Equations, Over a Finite Field / A.R. Woods
Multiplicative Complexity of Taylor Shifts and a New Twist of the Substitution Method / A. Schonhage
Local Search in Smooth Convex Sets / David Williamson ; R. Kannan ; A. NolteSession 4A:
A TDI System and its Application to Approximation Algorithms / M.-c. Cai ; X. Deng ; W. Zang
Geometric Separator Theorems and Applications / W.D. Smith ; N.C. Wormald
Approximation of Diameters: Randomization Doesn't Help / A. Brieden ; P. Gritzmann ; V. Klee ; L. Lovasz ; M. Simonovits
Time-Space Tradeoffs for Branching Programs / Allan Borodin ; P. Beame ; M. Saks ; J.S. ThathacharSession 4B:
Optimal Time-Space Trade-Offs for Sorting / J. Pagter ; T. Rauhe
Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions Over Finite Fields / D. Grigoriev ; A.A. Razborov
Lower Bounds for (MOD p-MOD m) Circuits / V. Grolmusz ; G. Tardos
On the Single-Source Unsplittable Flow Problem / Y. Dinitz ; N. Garg ; M.X. GoemansSession 5A:
Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems / J. Konemann
All Pairs Shortest Paths in Weighted Directed Graphs--Exact and Almost Exact Algorithms / U. Zwick
A Divide-and-Conquer Algorithm for Min-Cost Perfect Matching in the Plane / K.R. Varadarajan
1-Way Quantum Finite Automata: Strengths, Weaknesses and Generalizations / Edith Cohen ; A. Ambainis ; R. FreivaldsSession 5B:
The Quantum Communication Complexity of Sampling / A. Ta-Shma ; U. Vazirani ; A. Wigderson
Quantum Lower Bounds by Polynomials / R. Beals ; H. Buhrman ; R. Cleve ; M. Mosca ; R. de Wolf
Quantum Oracle Interrogation: Getting All Information for Almost Half the Price / W. van Dam
Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations / A. Frieze ; S. VempalaSession 6A:
Approximating a Finite Metric by a Small Number of Tree Metrics / C. Chekuri ; A. Goel ; S. Guha ; S Plotkin
Random Projection: A New Approach to VLSI Layout
Map Graphs in Polynomial Time / M. Thorup
On Learning Monotone Boolean Functions / A. Blum ; C. Burch ; J. LangfordSession 6B:
Orchestrating Quartets: Approximation and Data Correction / T. Jiang ; P. Kearney ; M. Li
Testing Monotonicity / O. Goldreich ; S. Goldwasser ; E. Lehman ; D. Ron
Evolutionary Trees can be Learned in Polynomial Time in the Two-State General Markov Model / M. Cryan ; L.A. Goldberg ; P.W. Goldberg
A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem / Joseph Naor ; K. JainSession 7A:
The Finite Capacity Dial-A-Ride Problem / B. Raghavachari
A Randomized Approximation Scheme for Metric MAX-CUT / W.F. de la Vega ; C. Kenyon
Semidefinite Relaxations for Parallel Machine Scheduling / M. Skutella
Lower Bounds for Zero Knowledge on the Internet / J. Kilian ; E. Petrank ; C. RackoffSession 7B:
Oblivious Transfer with a Memory-Bounded Receiver / C. Cachin ; C. Crepeau ; J. Marcil
Quantum Cryptography with Imperfect Apparatus / D. Mayers ; A. Yao
The Security of Individual RSA Bits / J. Hastad ; M. Naslund
Protocols for Asymmetric Communication Channels / M. Adler ; B.M. MaggsSession 8A:
Marked Ancestor Problems / S. Alstrup ; T. Husfeldt
Towards an Optimal Bit-Reversal Permutation Program / L. Carter ; K.S. Gatlin
The Minimum Equivalent DNF Problem and Shortest Implicants / C. UmansSession 8B:
Concurrent Reachability Games / L. de Alfaro ; T.A. Henzinger ; O. Kupferman
Perfect Information Leader Election in log* n + O (1) Rounds / A. Russell ; D. Zuckerman
Random Sampling, Halfspace Range Reporting, and Construction of ([less than or equal] k)-Levels in Three Dimensions / T.M. ChanSession 9A:
Parametric and Kinetic Minimum Spanning Trees / P.K. Agarwal ; D. Eppstein ; L.J. Guibas
On the Combinatorial and Topological Complexity of a Single Cell / S. Basu
Which Crossing Number is it, Anyway? / J. Pach ; G. Toth
An Improved Exponential-Time Algorithm for k-SAT / Toni Pitassi ; R. Paturi ; P. Pudlak ; M.E. Saks ; F. ZaneSession 9B:
Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems / M.L. Bonet ; J.L. Esteban ; N. Galesi ; J. Johannsen
Tseitin's Tautologies and Lower Bounds for Nullstellensatz Proofs
Which Problems Have Strongly Exponential Complexity? / R. Impagliazzo
Recommendation Systems: A Probabilistic Analysis / R. Kumar ; P. Raghavan ; S. Rajagopalan ; A. TomkinsSession 10A:
Heuristics for Finding Large Independent Sets, with Applications to Coloring Semi-Random Graphs / U. Feige
Improved Bounds and Algorithms for Hypergraph Two-Coloring / J. Radhakrishnan ; A. Srinivasan
Local Divergence of Markov Chains and the Analysis of Iterative Load-Balancing Schemes / Y. Rabani ; A. Sinclair ; R. Wanka
The Complexity of Acyclic Conjunctive Queries / G. Gottlob ; N. Leone ; F. ScarcelloSession 10B:
A Characterization of NC by Tree Recurrence / D. Leivant
A Linguistic Characterization of Bounded Oracle Computation and Probabilistic Polynomial Time / J. Mitchell ; M. Mitchell ; A. Scedrov
Randomness vs. Time: De-Randomization under a Uniform Assumption
Author Index
Foreword
Committees
Reviewers
7.

図書

図書
sponsored by IEEE Computer Society Technical Committee on Mathematical Foundations of Computing
出版情報: Los Alamitos, Calif. : IEEE Computer Society Press, c2000  xiv, 688 p. ; 28 cm
所蔵情報: loading…
目次情報: 続きを見る
Foreword
Committees
Reviewers
Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors / David Zuckerman ; O. Reingold ; S. Vadhan ; A. WigdersonSession 1:
Universality and Tolerance / N. Alon ; M. Capalbo ; Y. Kohayakawa ; V. Rodl ; A. Rucinski ; E. Szemeredi
Extracting Randomness via Repeated Condensing / R. Shaltiel
Extracting Randomness from Samplable Distributions / L. Trevisan
Pseudorandom Generators in Propositional Proof Complexity / M. Alekhnovich ; E. Ben-Sasson ; A. Razborov
Stochastic Models for the Web Graph / David Williamson ; R. Kumar ; P. Raghavan ; S. Rajagopalan ; D. Sivakumar ; A. Tomkins ; E. UpfalSession 2:
Optimization Problems in Congestion Control / R. Karp ; E. Koutsoupias ; C. Papadimitriou ; S. Shenker
Fairness Measures for Resource Allocation / A. Kumar ; J. Kleinberg
On the Approximability of Trade-offs and Optimal Access of Web Sources / M. Yannakakis
How Bad is Selfish Routing? / T. Roughgarden ; E. Tardos
A Polylogarithmic Approximation of the Minimum Bisection / Sanjeev Arora ; U. Feige ; R. KrauthgamerSession 3:
Approximability and In-Approximability Results for No-Wait Shop Scheduling / M. Sviridenko ; G. Woeginger
Nested Graph Dissection and Approximation Algorithms / S. Guha
Approximating the Single Source Unsplittable Min-Cost Flow Problem / M. Skutella
Hardness of Approximate Hypergraph Coloring / Michael Sipser ; V. Guruswami ; J. Hastad ; M. SudanSession 4:
"Soft-Decision" Decoding of Chinese Remainder Codes / A. Sahai
Super-Linear Time-Space Tradeoff Lower Bounds for Randomized Computation / P. Beame ; M. Saks ; X. Sun ; E. Vee
On the Hardness of Graph Isomorphism / J. Toran
Stable Distributions, Pseudorandom Generators, Embeddings and Data Stream Computation / R. Ravi ; P. IndykSession 5:
New Data Structures for Orthogonal Range Searching / S. Alstrup ; G. Brodal ; T. Rauhe
Nearly Optimal Expected-Case Planar Point Location / S. Arya ; T. Malamatos ; D. Mount
On Levels in Arrangements of Curves / T. Chan
Detecting a Network Failure / Avrim BlumSession 6:
Testing of Clustering / S. Dar ; M. Parnas ; D. Ron
Testing of Function That Have Small Width Branching Programs / I. Newman
Testing That Distributions Are Close / T. Batu ; L. Fortnow ; R. Rubinfeld ; W. Smith ; P. White
Using Upper Confidence Bounds for Online Learning / P. Auer
Zaps and Their Applications / Joe Kilian ; C. Dwork ; M. NaorSession 7:
Randomizing Polynomials: A New Representation with Applications to Round-Efficient Secure Computation / Y. Ishai ; E. Kushilevitz
Lower Bounds on the Efficiency of Generic Cryptographic Constructions / R. Gennaro
Concurrent Oblivious Transfer / J. Garay ; P. MacKenzie
The Relationship between Public Key Encryption and Oblivious Transfer / Y. Gertner ; S. Kannan ; T. Malkin ; M. Viswanathan
The Online Median Problem / Leonard Schulman ; R. Mettu ; C. PlaxtonSession 8:
Polynomial Time Approximation Schemes for Geometric k-Clustering / R. Ostrovsky ; Y. Rabani
Clustering Data Streams / N. Mishra ; R. Motwani ; L. O'Callaghan
On Clusterings--Good, Bad and Spectral / R. Kannan ; S. Vempala ; A. Vetta
Fully Dynamic Transitive Closure: Breaking through the O(n[superscript 2]) Barrier / C. Demetrescu ; G. ItalianoSession 9:
Opportunistic Data Structures with Applications / P. Ferragina ; G. Manzini
Cache-Oblivious B-Trees / M. Bender ; E. Demaine ; M. Farach-Colton
Using Expander Graphs to Find Vertex Connectivity / H. Gabow
On the Boundary Complexity of the Union of Fat Triangles / Mario Szegedy ; J. Pach ; G. TardosSession 10:
Straightening Polygonal Arcs and Convexifying Polygonal Cycles / R. Connelly ; G. Rote
A Combinatorial Approach to Planar Non-Colliding Robot Arm Motion Planning / I. Streinu
Topological Persistence and Simplification / H. Edelsbrunner ; D. Letscher ; A. Zomorodian
The Cover Time, the Blanket Time, and the Matthews Bound / Leslie Goldberg ; J. Kahn ; J. Kim ; L. Lovasz ; V. VuSession 11:
The Product Replacement Algorithm is Polynomial / I. Pak
Efficient Algorithms for Universal Portfolios / A. Kalai
Sampling Adsorbing Staircase Walks Using a New Markov Chain Decomposition Method / R. Martin ; D. Randall
The Randomness Recycler: A New Technique for Perfect Sampling / J. Fill ; M. Huber
An Improved Quantum Fourier Transform Algorithm and Applications / Umesh Vazirani ; L. Hales ; S. HallgrenSession 12:
Fast Parallel Circuits for the Quantum Fourier Transform / R. Cleve ; J. Watrous
Succinct Quantum Proofs for Properties of Finite Groups
Private Quantum Channels / A. Ambainis ; M. Mosca ; A. Tapp ; R. de Wolf
The Quantum Complexity of Set Membership / J. Radhakrishnan ; P. Sen ; S. Venkatesh
Randomized Rumor Spreading / C. Schindelhauer ; B. VockingSession 13:
Fast Broadcasting and Gossiping in Radio Networks / M. Chrobak ; L. Gasieniec ; W. Rytter
Linear Waste of Best Fit Bin Packing on Skewed Distributions / C. Kenyon ; M. Mitzenmacher
Optimal Myopic Algorithms for Random 3-SAT / D. Achlioptas ; G. Sorkin
Hierarchical Placement and Network Design Problems / A. Meyerson ; K. MunagalaSession 14:
Building Steiner Trees with Incomplete Global Knowledge / D. Karger ; M. Minkoff
Cost-Distance: Two Metric Network Design / S. Plotkin
Combinatorial Feature Selection Problems / M. Charikar
The Common Fragment of CTL and LTL / M. MaidlSession 15:
On the Existence of Booster Types / M. Herlihy ; E. Ruppert
Existential Second-Order Logic over Graphs: Charting the Tractability Frontier / G. Gottlob ; P. Kolaitis ; T. Schwentick
On Computing the Determinant and Smith Form of an Integer Matrix / W. Eberly ; M. Giesbrecht ; G. Villard
Author Index
Foreword
Committees
Reviewers
8.

図書

図書
sponsored by IEEE Computer Society Technical society on Foundations of Computing
出版情報: Los Alamitos, Calif. ; Tokyo : IEEE Computer Society, c2003  xiii, 661 p. ; 28 cm
所蔵情報: loading…
目次情報: 続きを見る
Foreword
Conference Organization and Program Committee
Reviewers
Machine Learning: My Favorite Results, Directions, and Open Problems / A. BlumTutorial 1:
Mixing / D. RandallTutorial 2:
Performance Analysis of Dynamic Network Processes / E. UpfalTutorial 3:
A Polynomial Algorithm for Recognizing Perfect Graphs / G. Cornuejols ; X. Liu ; K. VuskovicSession 1:
On Certain Connectivity Properties of the Internet Topology / M. Mihail ; C. Papadimitriou ; A. Saberi
Paths, Trees, and Minimum Latency Tours / K. Chaudhuri ; B. Godfrey ; S. Rao ; K. Talwar
Approximation Algorithms for Orienteering and Discounted-Reward TSP / S. Chawla ; D. Karger ; T. Lane ; A. Meyerson ; M. Minkoff
Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs / H. Kaplan ; M. Lewenstein ; N. Shafrir ; M. Sviridenko
On the Implementation of Huge Random Objects / O. Goldreich ; S. Goldwasser ; A. NussboimSession 2:
Zero-Knowledge Sets / S. Micali ; M. Rabin ; J. Kilian
Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography / J. Kamp ; D. Zuckerman
On the (In)security of the Fiat-Shamir Paradigm / Y. Kalai
Locally Testable Cyclic Codes / L. Babai ; A. Shpilka ; D. StefankovicSession 3:
List Decoding Using the XOR Lemma / L. Trevisan
On [eta]-Biased Generators in NC[superscript 0] / E. Mossel
Proving Hard-Core Predicates Using List Decoding / A. Akavia ; S. Safra
Instability of FIFO at Arbitrarily Low Rates in the Adversarial Queueing Model / R. Bhattacharjee ; A. GoelSession 4:
Proofs of the Parisi and Coppersmith-Sorkin Conjectures for the Finite Random Assignment Problem / C. Nair ; B. Prabhakar ; M. Sharma
Always Good Turing: Asymptotically Optimal Probability Estimation / A. Orlitsky ; N. Santhanam ; J. Zhang
Learning DNF from Random Walks / N. Bshouty ; R. O'Donnell ; R. Servedio
Quantum Search of Spatial Regions / S. Aaronson ; A. AmbainisSession 5:
A Lattice Problem in Quantum NP / D. Aharonov ; O. Regev
A Lower Bound for Bounded Round Quantum Communication Complexity of Set Disjointness / R. Jain ; J. Radhakrishnan ; P. Sen
Polynomial Degree vs. Quantum Query Complexity
An In-Place Sorting with O(n log n) Comparisons and O(n) Moves / G. Franceschini ; V. GeffertSession 6:
Breaking a Time-and-Space Barrier in Constructing Full-Text Indices / W.-K. Hon ; K. Sadakane ; W.-K. Sung
I/O-Efficient Strong Connectivity and Depth-First Search for Directed Planar Graphs / L. Arge ; N. Zeh
The Cost of Cache-Oblivious Searching / M. Bender ; G. Brodal ; R. Fagerberg ; D. Ge ; S. He ; H. Hu ; J. Iacono ; A. Lopez-Ortiz
Tight Lower Bounds for the Distinct Elements Problem / P. Indyk ; D. Woodruff
Hardness of Approximating the Shortest Vector Problem in High L[subscript p] Norms / S. KhotSession 7:
More on Average Case vs Approximation Complexity / M. Alekhnovich
On Worst-Case to Average-Case Reductions for NP Problems / A. Bogdanov
Rank Bounds and Integrality Gaps for Cutting Planes Procedures / J. Buresh-Oppenheim ; N. Galesi ; S. Hoory ; A. Magen ; T. Pitassi
The Resolution Complexity of Random Constraint Satisfaction Problems / M. Molloy ; M. SalavatipourSession 8:
Algorithms and Complexity Results for #SAT and Bayesian Inference / F. Bacchus ; S. Dalmao
Linear Upper Bounds for Random Walk on Small Density Random 3-CNFs / E. Ben-Sasson
On the Maximum Satisfiability of Random Formulas / D. Achlioptas ; A. Naor ; Y. Peres
Logics for Reasoning about Cryptographic Constructions / R. Impagliazzo ; B. KapronSession 9:
Lower Bounds for Non-Black-Box Zero Knowledge / B. Barak ; Y. Lindell ; S. Vadhan
General Composition and Universal Composability in Secure Multi-Party Computation
Bounded-Concurrent Secure Two-Party Computation in a Constant Number of Rounds / R. Pass ; A. Rosen
Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time O(m[superscript 1.31]) / D. Spielman ; S.-H. TengSession 10:
Separating the Power of Monotone Span Programs over Different Fields / A. Beimel ; E. Weinreb
A Group-Theoretic Approach to Fast Matrix Multiplication / H. Cohn ; C. Umans
Symmetric Polynomials over Z[subscript m] and Simultaneous Communication Protocols / N. Bhatnagar ; P. Gopalan ; R. Lipton
Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm / L. Becchetti ; S. Leonardi ; A. Marchetti-Spaccamela ; G. Schafer ; T. VredeveldSession 11:
Stability and Efficiency of a Random Local Load Balancing Protocol / A. Anagnostopoulos ; A. Kirsch
Gossip-Based Computation of Aggregate Information / D. Kempe ; A. Dobra ; J. Gehrke
Broadcasting Algorithms in Radio Networks with Unknown Topology / A. Czumaj ; W. Rytter
Switch Scheduling via Randomized Edge Coloring / G. Aggarwal ; R. Motwani ; D. Shah ; A. Zhu
On the Impossibility of Dimension Reduction in l1 / B. Brinkman ; M. CharikarSession 12:
Clustering with Qualitative Information / V. Guruswami ; A. Wirth
Bounded Geometries, Fractals, and Low-Distortion Embeddings / A. Gupta ; R. Krauthgamer ; J. Lee
On Levels in Arrangements of Curves, II: A Simple Inequality and Its Consequences / T. Chan
The Complexity of Homomorphism and Constraint Satisfaction Problems Seen from the Other Side / M. GroheSession 13:
Towards a Dichotomy Theorem for the Counting Constraint Satisfaction Problem / A. Bulatov ; V. Dalmau
Towards a Characterization of Truthful Combinatorial Auctions / R. Lavi ; A. Mu'alem ; N. NisanSession 14:
Group Strategyproof Mechanisms via Primal-Dual Algorithms / M. Pal ; E. Tardos
The Value of Knowing a Demand Curve: Bounds on Regret for Online Posted-Price Auctions / R. Kleinberg ; T. Leighton
Approximation Via Cost-Sharing: A Simple Approximation Algorithm for the Multicommodity Rent-or-Buy Problem / A. Kumar ; T. Roughgarden
A Non-Markovian Coupling for Randomly Sampling Colorings / T. Hayes ; E. VigodaSession 15:
The Ising Model on Trees: Boundary Conditions and Mixing Time / F. Martinelli ; A. Sinclair ; D. Weitz
Logconcave Functions: Geometry and Efficient Sampling Algorithms / L. Lovasz ; S. Vempala
Simulated Annealing in Convex Bodies and an O*(n[superscript 4]) Volume Algorithm
Author Index
Foreword
Conference Organization and Program Committee
Reviewers
9.

図書

図書
sponsored by IEEE Computer Society Technical Committee on Mathematical Foundations of Computing (TCMF) ; in cooperation with ACM/SIGACT
出版情報: Los Alamitos, Calif. ; Tokyo : IEEE Computer Society, c2002  xvi, 813 p. ; 28 cm
所蔵情報: loading…
10.

図書

図書
sponsored by the IEEE Computer Society's Technical Committee on Mathematical Foundations of Computing
出版情報: Washington, D.C. : IEEE Computer Society Press, c1985  xii, 552 p. ; 28 cm
所蔵情報: loading…
文献の複写および貸借の依頼を行う
 文献複写・貸借依頼