close
1.

図書

図書
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…
2.

図書

図書
sponsored by the IEEE Computer Society's Technical Committee on Mathematical Foundations of Computing, in cooperation with the ACM Special Interest Group for Automata and Computability Theory, Rice University, Departments of Mathematical Sciences and Electrical Engineering, the University of Houston, Department of Computer Science
出版情報: Long Beach, CA : IEEE Computer Society, c1976  276 p. ; 28 cm
所蔵情報: loading…
3.

図書

図書
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…
4.

図書

図書
sponsored by the IEEE Computer Society's Technical Committee on Mathematical Foundations of Computing, in cooperation with the ACM Special Interest Group for Automata and Computability Theory, and Brown University
出版情報: New York, N.Y. : Institute of Electrical and Electronics Engineers, c1977  v, 269 p. ; 28 cm
所蔵情報: loading…
5.

図書

図書
sponsored by the IEEE Computer Society's Technical Committee on Mathematical Foundations of Computing
出版情報: New York : Institute of Electrical and Electronics Engineers, c1980  421 p. ; 28 cm
所蔵情報: loading…
6.

図書

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

図書

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

図書

図書
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…
9.

図書

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

図書

図書
sponsored by IEEE Computer Society, IEEE Computer Society Technical Committee on Mathematical Foundations of Computing
出版情報: Los Alamitos, Calif. : IEEE Computer Society Press, c1996  xii, 638 p. ; 28 cm
所蔵情報: loading…
文献の複写および貸借の依頼を行う
 文献複写・貸借依頼