close
1.

図書
図書
1. Proceedings, Fourteenth Annual IEEE Conference on Computational Complexity (formerly: Structure in Complexity Theory Conference), May 4-6, 1999, Atlanta, Georgia, USA (: case ; : soft ; : microfiche)
sponsored by IEEE Computer Society Technical Committee on Mathematical Foundations of Computing ; in cooperation with ACM-SIGACT, EATCS
出版情報: Los Alamitos, Calif. : IEEE Computer Society, c1999  x, 241 p. ; 28 cm
所蔵情報: loading…
2.

図書
図書
2. Proceedings, Twelfth Annual IEEE Conference on Computational Complexity (formerly: Structure in Complexity Theory Conference), June 24-27, Ulm, Germany (: soft. ; : case.)
sponsored by the IEEE Computer Society Technical Committee on Mathematical Foundations of Computing ; in cooperation with ACM-SIGACT and EATCS ; with support from Ulmer Univeritäts-Gesellschaft ... [et al.]
出版情報: Los Alamitos, Calif. : IEEE Computer Society, c1997  x, 315 p. ; 28 cm
所蔵情報: loading…
3.

図書
図書
3. Proceedings, Thirteenth Annual IEEE Conference on Computational Complexity (formerly: Structure in Complexity Theory Conference), June 15-18, 1998, Buffalo, New York, USA (: soft ; : case ; : microfiche)
sponsored by IEEE Computer Society Technical Committee on Mathematical Foundations of Computing ; in cooperation with ACM-SIGACT, EATCS
出版情報: Los Alamitos, Calif. : IEEE Computer Society, c1998  ix, 281 p. ; 28 cm
所蔵情報: loading…
4.

図書
図書
4. Proceedings, Eleventh Annual IEEE Conference on Computational Complexity (formerly: Structure in Complexity Theory Conference), May 24-27, 1996, Philadelphia, Pennsylvania (: soft. ; : case.)
sponsored by IEEE Computer Society, IEEE Computer Society Technical Committee on Mathematical Foundations of Computing ; in cooperation with ACM SIGACT, EATCS ; with support from State University of New York at Buffalo ; edited by Steve Homer and Jin-Yi Cai
出版情報: Los Alamitos : IEEE Computer Society Press, c1996  x, 307 p. ; 28 cm
所蔵情報: loading…
5.

図書
図書
5. Proceedings, 18th IEEE Annual Conference on Computational Complexity, 7-10 July 2003, Aarhus, Denmark
sponsored by IEEE Computer Society Technical Committee on Mathematical Foundations of Computing (TCMF) ; in cooperation with ACM SIGACT, EATCS
出版情報: Los Alamitos, Calif. : IEEE Computer Society, c2003  xiii, 387 p. ; 28 cm
所蔵情報: loading…
6.

図書
図書
6. Proceedings : twentieth Annual IEEE Conference on Computational Complexity : 11-15 June 2005, San Jose, CA
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…
7.

図書
図書
7. Proceedings, 15th Annual IEEE Conference on Computational Complexity, July 4-7, 2000, Florence, Italy (: pbk ; : case ; : microfiche)
sponsored by IEEE Computer Society Technical Committee for Mathematical Foundations of Computing ; in cooperation with ACM-SIGACT, EATCS
出版情報: Los Alamitos, Calif. : IEEE Computer Society, c2000  x, 279 p. ; 28 cm
所蔵情報: loading…
目次情報: 続きを見る
Preface
Committees
Ron Book Prize for Best Student Paper
Time-Space Tradeoff Lower Bounds for Non-Uniform Computation / P. Beame
Time-Space Tradeoffs for Nondeterministic Computation / L. Fortnow ; D. van Melkebeek
A Lower Bound for the Shortest Path Problem / K. Mulmuley ; P. Shah
Time-Space Lower Bounds for SAT on Uniform and Non-Uniform Machines / I. Tourlakis
BP (f) = O (L (f)[superscript 1+varepsilon]) / O. Giel
The Communication Complexity of Enumeration, Elimination, and Selection / A. Ambainis ; H. Buhrman ; W. Gasarch ; B. Kalyanasundaram ; L. Torenvliet
The Query Complexity of Order-Finding / R. Cleve
On the Complexity of Some Problems on Groups Input as Multiplication Tables / D. Barrington ; P. Kadau ; K-J. Lange ; P. McKenzie
The Complexity of Tensor Calculus / C. Damm ; M. Holzer
The Complexity of Verifying the Characteristic Polynomial and Testing Similarity / T. Hoang ; T. Thierauf
A Dual Version of Reimer's Inequality and a Proof of Rudich's Conjecture / J. Kahn ; M. Saks ; C. Smyth
Computational Complexity and Phase Transitions / G. Istrate
An Application of Matroid Theory to the SAT Problem / O. Kullmann
New Bounds for the Language Compression Problem / S. Laplante ; P. Miltersen
Combinatorial Interpretation of Kolmogorov Complexity / A. Romashchenko ; A. Shen ; N. Vereshchagin
Independent Minimum Length Programs to Translate between Given Strings / N. Vereschagin ; M. Vyugin
A Survey of Optimal PCP Characterizations of NP / L. Trevisan
Easiness Assumptions and Hardness Tests: Trading Time for Zero Error / V. Kabanets
Dimension in Complexity Classes / J. Lutz
Average Case Complexity of Unbounded Fanin Circuits / A. Jakoby ; R. Reischuk
On the Hardness of 4-Coloring a 3-Colorable Graph / V. Guruswami ; S. Khanna
Deciding the K-Dimension is PSPACE-Complete / M. Schaefer
Integer Circuit Evaluation is PSPACE-Complete / K. Yang
A Separation of Determinism, Las Vegas and Nondeterminism for Picture Recognition / P. Duris ; J. Hromkovic ; K. Inoue
On the Complexity of Intersecting Finite State Automata / G. Karakostas ; R. Lipton ; A. Viglas
On the Complexity of the Monotonicity Verification / A. Voronenko
What Complexity and Cryptography Can Teach Each Other / R. Impagliazzo
Quantum Kolmogorov Complexity / A. Berthiaume ; W. van Dam
On the Complexity of Quantum ACC / F. Green ; S. Homer ; C. Pollett
Three Approaches to the Quantitative Definition of Information in an Individual Pure Quantum State / P. Vitanyi
Characterization of Non-Deterministic Quantum Query and Quantum Communication Complexity / R. de Wolf
Author Index
Preface
Committees
Ron Book Prize for Best Student Paper
8.

図書
図書
8. Proceedings, 17th Annual IEEE Conference on Computational Complexity, 21-24 May, 2002, Montreal, Canada (: pbk ; : case ; : microfiche)
sponsored by IEEE Computer Society Technical Committee on Mathematical Foundations of Computing (TCMF) ; in cooperation with SIGACT and EATCS
出版情報: Los Alamitos, Calif. : IEEE Computer Society, c2002  xii, 205 p. ; 28 cm
所蔵情報: loading…
目次情報: 続きを見る
Preface
Committees
Ron Book Prize for Best Student Paper
2002 Best Paper Award
Joint Session with STOC 2002 / Session 1：
Resolution Lower Bounds for the Weak Pigeonhole Principle / R. Raz
Hard Examples for Bounded Depth Frege / E. Ben-Sasson
Relations between Average Case Complexity and Approximation Complexity / U. Feige
Vertex Cover on 4-Regular Hyper-graphs Is Hard to Approximate within 2-[epsilon] / J. Holmerin
Improved Cryptographic Hash Functions with Worst-Case/Average-Case Connection / D. MicciancioSession 2：
Algorithmic Derandomization via Complexity Theory / D. Sivakumar
Pseudo-random Generators for All Hardnesses / C. Umans
Randomness Conductors and Constant-Degree Lossless Expanders / M. Capalbo ; O. Reingold ; S. Vadhan ; A. WigdersonSession 3：
Expanders from Symmetric Codes / R. Meshulam
The Complexity of Approximating the Entropy / T. Batu ; S. Dasgupta ; R. Kumar ; R. Rubinfeld
Time-Space Tradeoffs, Multiparty Communication Complexity, and Nearest-Neighbor Problems / P. Beame ; E. Vee
On Communication over an Entanglement-Assisted Quantum Channel / A. Nayak ; J. Salzman
Hardness Amplification within NP / R. O'DonnellSession 4：
3-Manifold Knot Genus Is NP-Complete / I. Agol ; J. Hass ; W. Thurston
On the Power of Unique 2-Prover 1-Round Games / S. Khot
Learnability beyond AC[superscript 0] / J. Jackson ; A. Klivans ; R. Servedio
Resolution Lower Bounds for Perfect Matching Principles / A. RazborovSession 5：
Resolution Width-Size Trade-Offs for the Pigeon-Hole Principle / S. Dantchev
The Inapproximability of Lattice and Coding Problems with Preprocessing
Sampling Short Lattice Vectors and the Closest Lattice Vector Problem / M. Ajtai
Invited Address 1
The History of Complexity / Lance Fortnow
The Correlation between Parity and Quadratic Polynomials Mod 3 / F. GreenSession 6：
Functions That Have Read-Twice Constant Width Branching Programs Are Not Necessarily Testable / E. Fischer ; I. Newman
On the Complexity of Integer Multiplication in Branching Programs with Multiple Tests and in Read-Once Branching Programs with Limited Nondeterminism / P. Woelfel
Information Theory Methods in Communication Complexity / Z. Bar-Yossef ; T. JayramSession 7：
Extracting Quantum Entanglement (General Entanglement Purification Protocols) / A. Ambainis ; A. Smith ; K. Yang
Algebras of Minimal Rank over Perfect Fields / M. Blaser
Invited Address 2
Rapid Mixing / Peter Winkler
Pseudorandomness and Average-Case Complexity via Uniform Reductions / L. TrevisanSession 8：
Pseudo-random Generators and Structure of Complete Degrees / M. Agrawal
Decoding Concatenated Codes Using Soft Information / V. Guruswami ; M. Sudan
Survey Talk 1
Arthur and Merlin in a Quantum World / John Watrous
Streaming Computation of Combinatorial Objects / R. ShaltielSession 9：
Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval / O. Goldreich ; H. Karloff ; L. Schulman
Better Lower Bounds for Locally Decodable Codes / A. Deshpande ; R. Jain ; T. Kavitha ; S. Lokam ; J. Radhakrishnan
Universal Arguments and Their Applications / B. Barak
Author Index
Preface
Committees
Ron Book Prize for Best Student Paper
9.

図書
図書
9. Proceedings, 16th Annual IEEE Conference on Computational Complexity, June 18-21, 2001, Chicago, Illinois (: pbk ; : case ; : microfiche)
sponsored by IEEE Computer Society Technical Committee for Mathematical Foundations of Computing ; in cooperation with ACM-SIGACT, EATCS
出版情報: Los Alamitos, Calif. : IEEE Computer Society, c2001  xiii, 303 p. ; 28 cm
所蔵情報: loading…
目次情報: 続きを見る
Dedication
Preface
Conference Organization
Best Paper Award
Ron Book Prize for Best Student Paper
In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time / R. Impagliazzo ; V. Kabanets ; A. WigdersonSession 1：
Towards Uniform AC[superscript 0]-Ismorphisms / M. Agrawal
Universal Traversal Sequences with Backtracking / M. Koucky
Comparing Notions of Full Derandomization / L. Fortnow
Monotone Simulations of Nonmonotone Proofs / A. Atserias ; N. Galesi ; P. PudlakSession 2：
Space Complexity of Random Formulae in Resolution / E. Ben-Sasson
Resolution Complexity of Independent Sets in Random Graphs / P. Beame ; A. Sabharwal
Tree Resolution Proofs of the Weak Pigeon-Hole Principle / S. Dantchev ; S. Riis
Separation of NP-Completeness Notions / A. Pavan ; A. SelmanSession 3：
Bounded Query Functions with Limited Output Bits / R. Chang ; J. Squire
A Linear Lower Bound on the Unbounded Error Probabilistic Communication Complexity / J. ForsterSession 4：
Towards Proving Strong Direct Product Theorems / R. Shaltiel
Communication Complexity Lower Bounds by Polynomials / H. Buhrman ; R. de WolfSession 5：
Quantum Algorithms for Element Distinctness / C. Durr ; M. Heiligman ; P. Hoyer ; F. Magniez ; M. Santha
Quantum versus Classical Learnability / R. Servedio ; S. Gortler
Uniform Circuits for Division: Consequences and Problems / E. Allender ; D. Barrington ; W. HesseSession 6：
Affine Projections of Symmetric Polynomials / A. Shpilka
On the Non-Approximability of Boolean Functions by OBDDs and Read-K-Times Branching Programs / B. Bollig ; M. Sauerhoff ; I. Wegener
Lower Bounds for Approximations by Low Degree Polynomials Over Zm / N. Alon ; R. Beigel
On the Power of Nonlinear Secret-Sharing / A. Beimel ; Y. Ishai
A Stronger Kolmogorov Zero-One Law for Resource-Bounded Measure / J. DaiSession 7：
Hausdorff Dimension in Exponential Time / K. Ambos-Spies ; W. Merkle ; J. Reimann ; F. Stephan
On the Complexity of Approximating the VC Dimension / E. Mossel ; C. UmansSession 8：
Links Between Complexity Theory and Constrained Block Coding / L. Stockmeyer ; D. Modha
Simple Analysis of Graph Tests for Linearity and PCP / J. Hastad
Logical Operations and Kolmogorov Complexity II / A. Muchnik ; N. VereshchaginSession 9：
Computational Depth / L. Antunes ; D. van Melkebeek
Quantum Algorithmic Entropy / P. Gacs
On Separators, Segregators and Time versus Space / R. SanthanamSession 10：
Time-Space Tradeoffs in the Counting Hierarchy / D. Ronneburger ; S. Roy ; V. Vinay
Author Index
Dedication
Preface
Conference Organization
10.

図書
図書
10. Proceedings : 19th IEEE Annual Conference on Computational Complexity : 21-24 June 2004, Amherst, Massachusetts
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
文献の複写および貸借の依頼を行う
 文献複写・貸借依頼