Volume 39; Issue 7

SIAM Journal on Computing

Volume 39; Issue 7
1

Chosen-Ciphertext Security via Correlated Products

Rosen, Alon, Segev, Gil
Journal:
SIAM Journal on Computing
Year:
2010
Language:
english
File:
PDF, 443 KB
english, 2010
2

Line Transversals of Convex Polyhedra in $\mathbb{R}^3$

Kaplan, Haim, Rubin, Natan, Sharir, Micha
Journal:
SIAM Journal on Computing
Year:
2010
Language:
english
File:
PDF, 606 KB
english, 2010
5

Approximating Steiner Networks with Node-Weights

Nutov, Zeev
Journal:
SIAM Journal on Computing
Year:
2010
Language:
english
File:
PDF, 349 KB
english, 2010
8

Fault Tolerant Spanners for General Graphs

Chechik, S., Langberg, M., Peleg, D., Roditty, L.
Journal:
SIAM Journal on Computing
Year:
2010
Language:
english
File:
PDF, 306 KB
english, 2010
9

Approximately Counting Integral Flows and Cell-Bounded Contingency Tables

Cryan, Mary, Dyer, Martin, Randall, Dana
Journal:
SIAM Journal on Computing
Year:
2010
Language:
english
File:
PDF, 302 KB
english, 2010
10

Adaptive Local Ratio

Mestre, Julián
Journal:
SIAM Journal on Computing
Year:
2010
Language:
english
File:
PDF, 282 KB
english, 2010
11

Approximate Halfspace Range Counting

Aronov, Boris, Sharir, Micha
Journal:
SIAM Journal on Computing
Year:
2010
Language:
english
File:
PDF, 313 KB
english, 2010
12

An $O(1)$ RMRs Leader Election Algorithm

Golab, Wojciech, Hendler, Danny, Woelfel, Philipp
Journal:
SIAM Journal on Computing
Year:
2010
Language:
english
File:
PDF, 686 KB
english, 2010
13

Quantum Computation and the Evaluation of Tensor Networks

Arad, Itai, Landau, Zeph
Journal:
SIAM Journal on Computing
Year:
2010
Language:
english
File:
PDF, 614 KB
english, 2010
14

On the Implementation of Huge Random Objects

Goldreich, Oded, Goldwasser, Shafi, Nussboim, Asaf
Journal:
SIAM Journal on Computing
Year:
2010
Language:
english
File:
PDF, 689 KB
english, 2010
15

Hardness Amplification Proofs Require Majority

Shaltiel, Ronen, Viola, Emanuele
Journal:
SIAM Journal on Computing
Year:
2010
Language:
english
File:
PDF, 417 KB
english, 2010
16

A Better Algorithm for Random k -SAT

Coja-Oghlan, Amin
Journal:
SIAM Journal on Computing
Year:
2010
Language:
english
File:
PDF, 499 KB
english, 2010
17

Approximate Hypergraph Partitioning and Applications

Fischer, Eldar, Matsliah, Arie, Shapira, Asaf
Journal:
SIAM Journal on Computing
Year:
2010
Language:
english
File:
PDF, 422 KB
english, 2010
19

Extensional Uniformity for Boolean Circuits

McKenzie, Pierre, Thomas, Michael, Vollmer, Heribert
Journal:
SIAM Journal on Computing
Year:
2010
Language:
english
File:
PDF, 327 KB
english, 2010
20

Local Monotonicity Reconstruction

Saks, Michael, Seshadhri, C.
Journal:
SIAM Journal on Computing
Year:
2010
Language:
english
File:
PDF, 475 KB
english, 2010
21

Unique Games with Entangled Provers Are Easy

Kempe, Julia, Regev, Oded, Toner, Ben
Journal:
SIAM Journal on Computing
Year:
2010
Language:
english
File:
PDF, 319 KB
english, 2010
23

Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding

Kawachi, Akinori, Yamakami, Tomoyuki
Journal:
SIAM Journal on Computing
Year:
2010
Language:
english
File:
PDF, 388 KB
english, 2010
24

Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes

Aronov, Boris, Ezra, Esther, Sharir, Micha
Journal:
SIAM Journal on Computing
Year:
2010
Language:
english
File:
PDF, 475 KB
english, 2010
26

An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods

Asadpour, Arash, Saberi, Amin
Journal:
SIAM Journal on Computing
Year:
2010
Language:
english
File:
PDF, 291 KB
english, 2010
27

Left-to-Right Multiplication for Monotone Boolean Dualization

Boros, Endre, Elbassioni, Khaled, Makino, Kazuhisa
Journal:
SIAM Journal on Computing
Year:
2010
Language:
english
File:
PDF, 233 KB
english, 2010