By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 39, Issue 3, pp. 783-1218

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Pass-Efficient Algorithms for Learning Mixtures of Uniform Distributions

Kevin L. Chang and Ravi Kannan

pp. 783-812

BibTeX  Abstract Full Text:  PDF

Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem

Sofya Raskhodnikova, Dana Ron, Amir Shpilka, and Adam Smith

pp. 813-842

BibTeX  Abstract Full Text:  PDF

Conditional Hardness for Approximate Coloring

Irit Dinur, Elchanan Mossel, and Oded Regev

pp. 843-873

BibTeX  Abstract Full Text:  PDF

An LLL Algorithm with Quadratic Complexity

Phong Q. Nguyen and Damien Stehlé

pp. 874-903

BibTeX  Abstract Full Text:  PDF

Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time

Artur Czumaj and Christian Sohler

pp. 904-922

BibTeX  Abstract Full Text:  PDF

On Coresets for $k$-Median and $k$-Means Clustering in Metric and Euclidean Spaces and Their Applications

Ke Chen

pp. 923-947

BibTeX  Abstract Full Text:  PDF

Tight Bounds for Randomized and Quantum Local Search

Shengyu Zhang

pp. 948-977

BibTeX  Abstract Full Text:  PDF
SPECIAL SECTION

Special Section On The Thirty-Ninth Annual ACM Symposium On Theory Of Computing (STOC 2007)

Eric Allender, Vladlen Koltun, and Maxim Sviridenko

p. 978

BibTeX  Abstract Full Text:  PDF

Faster Integer Multiplication

Martin Fürer

pp. 979-1005

BibTeX  Abstract Full Text:  PDF

Low-End Uniform Hardness versus Randomness Tradeoffs for AM

Ronen Shaltiel and Christopher Umans

pp. 1006-1037

BibTeX  Abstract Full Text:  PDF

Circuit Lower Bounds for Merlin–Arthur Classes

Rahul Santhanam

pp. 1038-1061

BibTeX  Abstract Full Text:  PDF

Survivable Network Design with Degree or Order Constraints

Lap Chi Lau, Joseph (Seffi) Naor, Mohammad R. Salavatipour, and Mohit Singh

pp. 1062-1087

BibTeX  Abstract Full Text:  PDF

Playing Games with Approximation Algorithms

Sham M. Kakade, Adam Tauman Kalai, and Katrina Ligett

pp. 1088-1106

BibTeX  Abstract Full Text:  PDF

Linear Probing with Constant Independence

Anna Pagh, Rasmus Pagh, and Milan Ružić

pp. 1107-1120

BibTeX  Abstract Full Text:  PDF

Zero-Knowledge Proofs from Secure Multiparty Computation

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai

pp. 1121-1152

BibTeX  Abstract Full Text:  PDF

Statistically Hiding Commitments and Statistical Zero-Knowledge Arguments from Any One-Way Function

Iftach Haitner, Minh-Huyen Nguyen, Shien Jin Ong, Omer Reingold, and Salil Vadhan

pp. 1153-1218

BibTeX  Abstract Full Text:  PDF