Computational complexity. proceedings : 17th IEEE Annual Conference on Computational Complexity : 21-24 May, 2002, Montreal, Canada / sponsored by The IEEE Computer Society, Technical Committee on Mathematical Foundations of Computing ; in cooperation with SIGACT ... [and others].

Format:

Book

Conference/Event

Contributor:

IEEE Xplore (Online service)

IEEE Computer Society. Technical Committee on Mathematical Foundations of Computing.

ACM Special Interest Group for Algorithms and Computation Theory

Conference Name:

IEEE Conference on Computational Complexity (17th : 2002 : Montreal, Québec)

Language:

English

Subjects (All):

Computational complexity--Congresses.

Computational complexity.

Nonlinear boundary value problems--Congresses.

Nonlinear boundary value problems.

Polynomials--Congresses.

Polynomials.

Logic programming--Congresses.

Logic programming.

Genre:

Conference papers and proceedings.

Physical Description:

xii, 205 pages : illustrations

Other Title:

17th Annual IEEE Conference on Computational Complexity

Computational complexity, 2002, proceedings, 17th IEEE Annual Conference on.

Place of Publication:

Los Alamitos, Calif. : IEEE Computer Society, [2002]

System Details:

Mode of access: World Wide Web.

text file

Contents:

Session 1 Joint Session with STOC 2002 / Chair: Sam Buss

Resolution Lower Bounds for the Weak Pigeonhole Principle / R. Raz 3

Hard Examples for Bounded Depth Frege / E. Ben-Sasson 4

Relations between Average Case Complexity and Approximation Complexity / U. Feige 5

Vertex Cover on 4-Regular Hyper-graphs Is Hard to Approximate within 2-[epsilon] / J. Holmerin 6

Session 2 Joint Session with STOC 2002 / Chair: Anne Condon

Improved Cryptographic Hash Functions with Worst-Case/Average-Case Connection / D. Micciancio 9

Algorithmic Derandomization via Complexity Theory / D. Sivakumar 10

Pseudo-random Generators for All Hardnesses / C. Umans 11

Session 3 Joint Session with STOC 2002 / Chair: Michael Saks

Randomness Conductors and Constant-Degree Lossless Expanders / M. Capalbo, O. Reingold, S. Vadhan, A. Wigderson 15

Expanders from Symmetric Codes / R. Meshulam, A. Wigderson 16

The Complexity of Approximating the Entropy / T. Batu, S. Dasgupta, R. Kumar, R. Rubinfeld 17

Time-Space Tradeoffs, Multiparty Communication Complexity, and Nearest-Neighbor Problems / P. Beame, E. Vee 18

On Communication over an Entanglement-Assisted Quantum Channel / A. Nayak, J. Salzman 19

Session 4 Joint Session with STOC 2002 / Chair: Sam Buss

Hardness Amplification within NP / R. O'Donnell 23

3-Manifold Knot Genus Is NP-Complete / I. Agol, J. Hass, W. Thurston 24

On the Power of Unique 2-Prover 1-Round Games / S. Khot 25

Learnability beyond AC[superscript 0] / J. Jackson, A. Klivans, R. Servedio 26

Resolution Lower Bounds for Perfect Matching Principles / A. Razborov 29

Resolution Width-Size Trade-Offs for the Pigeon-Hole Principle / S. Dantchev 39

The Inapproximability of Lattice and Coding Problems with Preprocessing / U. Feige, D. Micciancio 44

Sampling Short Lattice Vectors and the Closest Lattice Vector Problem / M. Ajtai, R. Kumar, D. Sivakumar 53

Invited Address 1 / Chair: Harry Buhrman

The History of Complexity / Lance Fortnow 61

The Correlation between Parity and Quadratic Polynomials Mod 3 / F. Green 65

Functions That Have Read-Twice Constant Width Branching Programs Are Not Necessarily Testable / E. Fischer, I. Newman 73

On the Complexity of Integer Multiplication in Branching Programs with Multiple Tests and in Read-Once Branching Programs with Limited Nondeterminism / P. Woelfel 80

Information Theory Methods in Communication Complexity / Z. Bar-Yossef, T. Jayram, R. Kumar, D. Sivakumar 93

Extracting Quantum Entanglement (General Entanglement Purification Protocols) / A. Ambainis, A. Smith, K. Yang 103

Algebras of Minimal Rank over Perfect Fields / M. Blaser 113

Rapid Mixing / Peter Winkler 125

Pseudorandomness and Average-Case Complexity via Uniform Reductions / L. Trevisan, S. Vadhan 129

Pseudo-random Generators and Structure of Complete Degrees / M. Agrawal 139

Decoding Concatenated Codes Using Soft Information / V. Guruswami, M. Sudan 148

Survey Talk 1 / Chair: Jin-Yi Cai

Arthur and Merlin in a Quantum World / John Watrous 161

Streaming Computation of Combinatorial Objects / Z. Bar-Yossef, O. Reingold, R. Shaltiel, L. Trevisan 165

Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval / O. Goldreich, H. Karloff, L. Schulman, L. Trevisan 175

Better Lower Bounds for Locally Decodable Codes / A. Deshpande, R. Jain, T. Kavitha, S. Lokam, J. Radhakrishnan 184

Universal Arguments and Their Applications / B. Barak, O. Goldreich 194.

Notes:

Includes bibliographical references and author index.

"IEEE Computer Society Order Number PR01468"--T.p. verso.

ISBN:

0769514685

9780769514680

0769514693

9780769514697

0769514707

9780769514703

OCLC:

49937478

Access Restriction:

Restricted for use by site license.