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, 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
5.

図書

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

図書

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

図書

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

図書

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

図書

図書
Symposium on Foundations of Computer Science
出版情報: Piscataway, NJ : The Institute of Electrical and Electronics Engineers, Inc., c2008  773 p. ; 28 cm
所蔵情報: loading…
10.

図書

図書
Symposium on Foundations of Computer Science ; IEEE Computer Society
出版情報: Piscataway, N.J. : IEEE, c2009  xiv, 777 p. ; 28 cm
所蔵情報: loading…
文献の複写および貸借の依頼を行う
 文献複写・貸借依頼