Volume 47; Issue 6

SIAM Journal on Computing

Volume 47; Issue 6
1

Commutativity in the Algorithmic Lovász Local Lemma

Kolmogorov, Vladimir
Journal:
SIAM Journal on Computing
Year:
2018
Language:
english
File:
PDF, 564 KB
english, 2018
3

Near-Optimal Distributed Maximum Flow

Ghaffari, Mohsen, Karrenbauer, Andreas, Kuhn, Fabian, Lenzen, Christoph, Patt-Shamir, Boaz
Journal:
SIAM Journal on Computing
Year:
2018
Language:
english
File:
PDF, 1.31 MB
english, 2018
4

Minimum Cuts and Sparsification in Hypergraphs

Chekuri, Chandra, Xu, Chao
Journal:
SIAM Journal on Computing
Year:
2018
Language:
english
File:
PDF, 663 KB
english, 2018
5

Watermarking Cryptographic Capabilities

Cohen, Aloni, Holmgren, Justin, Nishimaki, Ryo, Vaikuntanathan, Vinod, Wichs, Daniel
Journal:
SIAM Journal on Computing
Year:
2018
Language:
english
File:
PDF, 620 KB
english, 2018
7

On Monotonicity Testing and Boolean Isoperimetric-type Theorems

Khot, Subhash, Minzer, Dor, Safra, Muli
Journal:
SIAM Journal on Computing
Year:
2018
Language:
english
File:
PDF, 583 KB
english, 2018
9

Pseudorandomness via the Discrete Fourier Transform

Gopalan, Parikshit, Kane, Daniel M., Meka, Raghu
Journal:
SIAM Journal on Computing
Year:
2018
Language:
english
File:
PDF, 522 KB
english, 2018
10

Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time

Lee, Yin Tat, Sun, He
Journal:
SIAM Journal on Computing
Year:
2018
Language:
english
File:
PDF, 412 KB
english, 2018
11

A Hierarchy of Lower Bounds for Sublinear Additive Spanners

Abboud, Amir, Bodwin, Greg, Pettie, Seth
Journal:
SIAM Journal on Computing
Year:
2018
Language:
english
File:
PDF, 684 KB
english, 2018
12

Deterministic Communication vs. Partition Number

Göös, Mika, Pitassi, Toniann, Watson, Thomas
Journal:
SIAM Journal on Computing
Year:
2018
Language:
english
File:
PDF, 448 KB
english, 2018
13

Sample(x)=(a*x

Thorup, Mikkel
Journal:
SIAM Journal on Computing
Year:
2018
Language:
english
File:
PDF, 428 KB
english, 2018
15

The Power of Asymmetry in Constant-Depth Circuits

Sherstov, Alexander A.
Journal:
SIAM Journal on Computing
Year:
2018
Language:
english
File:
PDF, 742 KB
english, 2018
16

Towards an Optimal Method for Dynamic Planar Point Location

Chan, Timothy M., Nekrich, Yakov
Journal:
SIAM Journal on Computing
Year:
2018
Language:
english
File:
PDF, 490 KB
english, 2018