Volume 45; Issue 4

SIAM Journal on Computing

Volume 45; Issue 4
1

Local Correlation Breakers and Applications to Three-Source Extractors and Mergers

Cohen, Gil
Journal:
SIAM Journal on Computing
Year:
2016
Language:
english
File:
PDF, 489 KB
english, 2016
3

Half-integrality, LP-branching, and FPT Algorithms

Iwata, Yoichi, Wahlström, Magnus, Yoshida, Yuichi
Journal:
SIAM Journal on Computing
Year:
2016
Language:
english
File:
PDF, 1.06 MB
english, 2016
5

Computing a Nonnegative Matrix Factorization---Provably

Arora, Sanjeev, Ge, Rong, Kannan, Ravi, Moitra, Ankur
Journal:
SIAM Journal on Computing
Year:
2016
Language:
english
File:
PDF, 395 KB
english, 2016
6

Robustly Solvable Constraint Satisfaction Problems

Barto, Libor, Kozik, Marcin
Journal:
SIAM Journal on Computing
Year:
2016
Language:
english
File:
PDF, 295 KB
english, 2016
8

Routing in Undirected Graphs with Constant Congestion

Chuzhoy, Julia
Journal:
SIAM Journal on Computing
Year:
2016
Language:
english
File:
PDF, 1.94 MB
english, 2016
9

The Multiparty Communication Complexity of Set Disjointness

Sherstov, Alexander A.
Journal:
SIAM Journal on Computing
Year:
2016
Language:
english
File:
PDF, 430 KB
english, 2016
13

The HOM Problem is EXPTIME-Complete

Creus, Carles, Gascón, Adrià, Godoy, Guillem, Ramos, Lander
Journal:
SIAM Journal on Computing
Year:
2016
Language:
english
File:
PDF, 416 KB
english, 2016
14

Upper and Lower Bounds on the Power of Advice

Chattopadhyay, Arkadev, Edmonds, Jeff, Ellen, Faith, Pitassi, Toniann
Journal:
SIAM Journal on Computing
Year:
2016
Language:
english
File:
PDF, 405 KB
english, 2016
15

Semantic Acyclicity on Graph Databases

Barceló, Pablo, Romero, Miguel, Vardi, Moshe Y.
Journal:
SIAM Journal on Computing
Year:
2016
Language:
english
File:
PDF, 460 KB
english, 2016