close
1.

図書

図書
sponsored by ACM SIGMOBILE ... [et al.] ; in cooperation with ACM SIGACT
出版情報: New York : Association for Computing Machinery, c2000  104 p. ; 28 cm
所蔵情報: loading…
2.

図書

図書
sponsored by ACM SIGACT, ACM SIGARCH ; in cooperation with EATCS
出版情報: New York : Association for Computing Machinery, c2002  viii, 294 p. ; 28 cm
所蔵情報: loading…
3.

図書

図書
Gene Myers ... [et al.], editors ; sponsored by Association for Computing Machinery, SIGACT ; with support from Celera ... [et al.]
出版情報: New York, N.Y. : Association for Computing Machinery, c2002  viii, 331 p. ; 28 cm
所蔵情報: loading…
4.

図書

図書
Thomas Lengauer ... [et al.], editors ; sponsored by Association for Computing Machinery, SIGACT ; with support from Celera Genomics ... [et al.]
出版情報: New York, N.Y. : Association for Computing Machinery, c2001  ix, 316 p. ; 28 cm
所蔵情報: loading…
5.

図書

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

図書

図書
sponsored by IEEE Computer Society Technical Committee on Mathematical Foundations of Computing (TCMF) ; in cooperation with ACM SIGACT
出版情報: Los Alamitos, Calif. : IEEE Computer Society, c2004  xi, 333 p. ; 28 cm
所蔵情報: loading…
目次情報: 続きを見る
Preface
Committees
Awards
ECCC 10th Anniversary
Compression of Samplable Sources / L. Trevisan ; S. Vadhan ; D. ZuckermanSession 1:
Language Compression and Pseudorandom Generators / H. Buhrman ; T. Lee ; D. van Melkebeek
On Pseudoentropy versus Compressibility / H. Wee
Reductions between Disjoint NP-Pairs / C. Glasser ; A. Selman ; S. SenguptaSession 2:
Relativized NP Search Problems and Propositional Proof Systems / J. Buresh-Oppenheim ; T. Morioka
The Complexity of Treelike Systems over [lambda]-Local Formulae / N. Galesi ; N. Thapen
Lower Bounds for Testing Bipartiteness in Dense Graphs / A. BogdanovSession 3:
Polylogarithmic-round Interactive Proofs for coNP Collapse the Exponential Hierarchy
Solvable Group Isomorphism is (almost) in NP [intersection of] CoNP / V. Arvind ; J. Toran
Small Spans in Scaled Dimension / J. Hitchcock
Computing in Fault Tolerance Broadcast Networks / I. NewmanSession 4:
Some Results on Majority Quantifiers over Words / K.-J. Lange
Separating Complexity Classes Using Structural Properties / L. Torenvliet
Parameterized Complexity of Constraint Satisfaction Problems / D. MarxSession 5:
Tight Lower Bounds for Certain Parameterized NP-Hard Problems / J. Chen ; B. Chor ; M. Fellows ; X. Huang ; D. Juedes ; I. Kanj ; G. Xia
The Complexity of the Covering Radius Problem on Lattices and Codes / V. Guruswami ; D. Micciancio ; O. Regev
Dimension, Entropy Rates, and Compression / N. VinodchandranSession 6:
Properties of NP-Complete Sets / A. Pavan
Partial Bi-immunity and NP-Completeness
Abelian Permutation Group Problems and Logspace Counting Classes / T. VijayaraghavanSession 7:
Deterministic Polynomial Identity Testing in Non-commutative Models / R. Raz ; A. Shpilka
Polynomials That Sign Represent Parity and Descartes Rule of Signs / S. Basu ; N. Bhatnagar ; P. Gopalan ; R. Lipton
Consequences and Limits of Nonlocal Strategies / R. Cleve ; P. Hoyer ; B. Toner ; J. WatrousSession 8:
Multiparty Quantum Coin Flipping / A. Ambainis ; Y. Dodis ; H. Rohrig
On the Power of Quantum Proofs
Quantum Arthur-Merlin Games / C. Marriott
Graph Properties and Circular Functions: How Low Can Quantum Query Complexity Go? / X. Sun ; A. Yao ; S. ZhangSession 9:
Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments / S. Laplante ; F. Magniez
Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information / K. Yang
Limitations of Quantum Advice and One-Way Communication / S. Aaronson
Author Index
Preface
Committees
Awards
7.

図書

図書
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
8.

図書

図書
sponsored by ACM SIGACT, ACM SIGARCH ; in cooperation with European Association for Theoretical Computer Science & Intel corporation
出版情報: New York : Association for Computing Machinery, c2004  x, 322 p. ; 28 cm
所蔵情報: loading…
9.

図書

図書
sponsored by the ACM Special Interest Group for Automata and Computability Theory, and ACM Special Interest Group for Operating System Principles
出版情報: New York, N.Y. : Association for Computing Machinery, c1997  viii, 297 p. ; 28 cm
所蔵情報: loading…
10.

図書

図書
sponsored by the ACM Special Interest Group for Automata and Computability Theory, and ACM Special Interest Group for Operating System Principles
出版情報: New York, N.Y. : Association for Computing Machinery, c1998  x, 328 p. ; 28 cm
所蔵情報: loading…
文献の複写および貸借の依頼を行う
 文献複写・貸借依頼