Volume 41; Issue 6

SIAM Journal on Computing

Volume 41; Issue 6
1

Max Cut and the Smallest Eigenvalue

Trevisan, Luca
Journal:
SIAM Journal on Computing
Year:
2012
Language:
english
File:
PDF, 265 KB
english, 2012
2

Agnostic Learning of Monomials by Halfspaces Is Hard

Feldman, Vitaly, Guruswami, Venkatesan, Raghavendra, Prasad, Wu, Yi
Journal:
SIAM Journal on Computing
Year:
2012
Language:
english
File:
PDF, 425 KB
english, 2012
3

Transitive-Closure Spanners

Bhattacharyya, Arnab, Grigorescu, Elena, Jung, Kyomin, Raskhodnikova, Sofya, Woodruff, David P.
Journal:
SIAM Journal on Computing
Year:
2012
Language:
english
File:
PDF, 779 KB
english, 2012
4

Locality from Circuit Lower Bounds

Anderson, Matthew, van Melkebeek, Dieter, Schweikardt, Nicole, Segoufin, Luc
Journal:
SIAM Journal on Computing
Year:
2012
Language:
english
File:
PDF, 784 KB
english, 2012
5

On the Hidden Shifted Power Problem

Bourgain, Jean, Garaev, Moubariz Z., Konyagin, Sergei V., Shparlinski, Igor E.
Journal:
SIAM Journal on Computing
Year:
2012
Language:
english
File:
PDF, 376 KB
english, 2012
6

Reconstructing Approximate Phylogenetic Trees from Quartet Samples

Snir, Sagi, Yuster, Raphael
Journal:
SIAM Journal on Computing
Year:
2012
Language:
english
File:
PDF, 302 KB
english, 2012
7

Fast Information Spreading in Graphs with Large Weak Conductance

Censor-Hillel, Keren, Shachnai, Hadas
Journal:
SIAM Journal on Computing
Year:
2012
Language:
english
File:
PDF, 326 KB
english, 2012
8

Homology Flows, Cohomology Cuts

Chambers, Erin W., Erickson, Jeff, Nayyeri, Amir
Journal:
SIAM Journal on Computing
Year:
2012
Language:
english
File:
PDF, 636 KB
english, 2012
9

Bit-Probe Lower Bounds for Succinct Data Structures

Viola, Emanuele
Journal:
SIAM Journal on Computing
Year:
2012
Language:
english
File:
PDF, 208 KB
english, 2012
10

Twice-Ramanujan Sparsifiers

Batson, Joshua, Spielman, Daniel A., Srivastava, Nikhil
Journal:
SIAM Journal on Computing
Year:
2012
Language:
english
File:
PDF, 258 KB
english, 2012
11

3-Query Locally Decodable Codes of Subexponential Length

Efremenko, Klim
Journal:
SIAM Journal on Computing
Year:
2012
Language:
english
File:
PDF, 199 KB
english, 2012
12

Approximating Edit Distance in Near-Linear Time

Andoni, Alexandr, Onak, Krzysztof
Journal:
SIAM Journal on Computing
Year:
2012
Language:
english
File:
PDF, 248 KB
english, 2012
13

Universally Utility-maximizing Privacy Mechanisms

Ghosh, Arpita, Roughgarden, Tim, Sundararajan, Mukund
Journal:
SIAM Journal on Computing
Year:
2012
Language:
english
File:
PDF, 321 KB
english, 2012
14

Online and Stochastic Survivable Network Design

Gupta, Anupam, Krishnaswamy, Ravishankar, Ravi, R.
Journal:
SIAM Journal on Computing
Year:
2012
Language:
english
File:
PDF, 361 KB
english, 2012
16

New Direct-Product Testers and 2-Query PCPs

Impagliazzo, Russell, Kabanets, Valentine, Wigderson, Avi
Journal:
SIAM Journal on Computing
Year:
2012
Language:
english
File:
PDF, 573 KB
english, 2012
17

Quantum Query Complexity of Minor-Closed Graph Properties

Childs, Andrew M., Kothari, Robin
Journal:
SIAM Journal on Computing
Year:
2012
Language:
english
File:
PDF, 392 KB
english, 2012