Volume 42; Issue 6

SIAM Journal on Computing

Volume 42; Issue 6
1

On the Power of Randomization in Algorithmic Mechanism Design

Dobzinski, Shahar, Dughmi, Shaddin
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 268 KB
english, 2013
2

Vertex Sparsification and Oblivious Reductions

Moitra, Ankur
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 300 KB
english, 2013
6

The Intersection of Two Halfspaces Has High Threshold Degree

Sherstov, Alexander A.
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 486 KB
english, 2013
7

On the Queue Number of Planar Graphs

Di Battista, Giuseppe, Frati, Fabrizio, Pach, János
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 758 KB
english, 2013
8

Subexponential Parameterized Algorithm for Minimum Fill-In

Fomin, Fedor V., Villanger, Yngve
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 525 KB
english, 2013
9

A Space Lower Bound for Dynamic Approximate Membership Data Structures

Lovett, Shachar, Porat, Ely
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 229 KB
english, 2013
10

Deterministic Algorithms for the Lovász Local Lemma

Chandrasekaran, Karthekeyan, Goyal, Navin, Haeupler, Bernhard
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 451 KB
english, 2013
11

Additive Approximation for Bounded Degree Survivable Network Design

Lau, Lap Chi, Singh, Mohit
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 530 KB
english, 2013
12

KKL, Kruskal--Katona, and Monotone Nets

O'Donnell, Ryan, Wimmer, Karl
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 321 KB
english, 2013
13

On Range Searching with Semialgebraic Sets. II

Agarwal, Pankaj K., Matoušek, Jiří, Sharir, Micha
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 303 KB
english, 2013
14

Dynamic and Nonuniform Pricing Strategies for Revenue Maximization

Chakraborty, Tanmoy, Huang, Zhiyi, Khanna, Sanjeev
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 313 KB
english, 2013
16

Composition of Low-Error 2-Query PCPs Using Decodable PCPs

Dinur, Irit, Harsha, Prahladh
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 384 KB
english, 2013
17

A Parallel Repetition Theorem for Any Interactive Argument

Haitner, Iftach
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 221 KB
english, 2013
18

On the Insertion Time of Cuckoo Hashing

Fountoulakis, Nikolaos, Panagiotou, Konstantinos, Steger, Angelika
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 307 KB
english, 2013