Volume 46; Issue 3

SIAM Journal on Computing

Volume 46; Issue 3
1

Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP

Cai, Jin-Yi, Lu, Pinyan, Xia, Mingji
Journal:
SIAM Journal on Computing
Year:
2017
Language:
english
File:
PDF, 585 KB
english, 2017
4

On the $AC^0$ Complexity of Subgraph Isomorphism

Li, Yuan, Razborov, Alexander, Rossman, Benjamin
Journal:
SIAM Journal on Computing
Year:
2017
Language:
english
File:
PDF, 637 KB
english, 2017
5

A PAC Approach to Application-Specific Algorithm Selection

Gupta, Rishi, Roughgarden, Tim
Journal:
SIAM Journal on Computing
Year:
2017
Language:
english
File:
PDF, 791 KB
english, 2017
6

Nearly Optimal NP-Hardness of Unique Coverage

Guruswami, Venkatesan, Lee, Euiwoong
Journal:
SIAM Journal on Computing
Year:
2017
Language:
english
File:
PDF, 189 KB
english, 2017
11

The Power of Oblivious Wireless Power

Halldórsson, Magnús M., Holzer, Stephan, Mitra, Pradipta, Wattenhofer, Roger
Journal:
SIAM Journal on Computing
Year:
2017
Language:
english
File:
PDF, 643 KB
english, 2017
12

The Complexity of General-Valued CSPs

Kolmogorov, Vladimir, Krokhin, Andrei, Rolínek, Michal
Journal:
SIAM Journal on Computing
Year:
2017
Language:
english
File:
PDF, 480 KB
english, 2017