Volume 40; Issue 3

SIAM Journal on Computing

Volume 40; Issue 3
3

A Counterexample to Strong Parallel Repetition

Raz, Ran
Journal:
SIAM Journal on Computing
Year:
2011
Language:
english
File:
PDF, 159 KB
english, 2011
4

Boltzmann Samplers, Pólya Theory, and Cycle Pointing

Bodirsky, Manuel, Fusy, Éric, Kang, Mihyun, Vigerske, Stefan
Journal:
SIAM Journal on Computing
Year:
2011
Language:
english
File:
PDF, 611 KB
english, 2011
5

Terminal Backup, 3D Matching, and Covering Cubic Graphs

Anshelevich, Elliot, Karagiozova, Adriana
Journal:
SIAM Journal on Computing
Year:
2011
Language:
english
File:
PDF, 509 KB
english, 2011
6

Optimal Envy-Free Pricing with Metric Substitutability

Chen, Ning, Ghosh, Arpita, Vassilvitskii, Sergei
Journal:
SIAM Journal on Computing
Year:
2011
Language:
english
File:
PDF, 381 KB
english, 2011
8

Entangled Games Are Hard to Approximate

Kempe, Julia, Kobayashi, Hirotada, Matsumoto, Keiji, Toner, Ben, Vidick, Thomas
Journal:
SIAM Journal on Computing
Year:
2011
Language:
english
File:
PDF, 376 KB
english, 2011
9

Kakeya Sets, New Mergers, and Old Extractors

Dvir, Zeev, Wigderson, Avi
Journal:
SIAM Journal on Computing
Year:
2011
Language:
english
File:
PDF, 232 KB
english, 2011
11

An Expansion Tester for Bounded Degree Graphs

Kale, Satyen, Seshadhri, C.
Journal:
SIAM Journal on Computing
Year:
2011
Language:
english
File:
PDF, 212 KB
english, 2011
12

Short Seed Extractors against Quantum Storage

Ta-Shma, Amnon
Journal:
SIAM Journal on Computing
Year:
2011
Language:
english
File:
PDF, 246 KB
english, 2011
14

Unifying the Landscape of Cell-Probe Lower Bounds

P traşcu, Mihai
Journal:
SIAM Journal on Computing
Year:
2011
Language:
english
File:
PDF, 303 KB
english, 2011
15

A Topological View of Unsupervised Learning from Noisy Data

Niyogi, P., Smale, S., Weinberger, S.
Journal:
SIAM Journal on Computing
Year:
2011
Language:
english
File:
PDF, 325 KB
english, 2011
16

What Can We Learn Privately?

Kasiviswanathan, Shiva Prasad, Lee, Homin K., Nissim, Kobbi, Raskhodnikova, Sofya, Smith, Adam
Journal:
SIAM Journal on Computing
Year:
2011
Language:
english
File:
PDF, 617 KB
english, 2011