Volume 42; Issue 3

SIAM Journal on Computing

Volume 42; Issue 3
1

Balls and Bins: Smaller Hash Families and Faster Evaluation

Celis, L. Elisa, Reingold, Omer, Segev, Gil, Wieder, Udi
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 305 KB
english, 2013
2

Computing the Girth of a Planar Graph in Linear Time

Chang, Hsien-Chih, Lu, Hsueh-I
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 431 KB
english, 2013
3

Every Property of Hyperfinite Graphs Is Testable

Newman, Ilan, Sohler, Christian
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 275 KB
english, 2013
4

Pseudorandom Generators for Combinatorial Shapes

Gopalan, Parikshit, Meka, Raghu, Reingold, Omer, Zuckerman, David
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 348 KB
english, 2013
5

Improving Exhaustive Search Implies Superpolynomial Lower Bounds

Williams, Ryan
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 362 KB
english, 2013
6

Finding, Minimizing, and Counting Weighted Subgraphs

Williams, Virginia Vassilevska, Williams, Ryan
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 339 KB
english, 2013
7

Graph Homomorphisms with Complex Values: A Dichotomy Theorem

Cai, Jin-Yi, Chen, Xi, Lu, Pinyan
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 1.19 MB
english, 2013
8

$\mathcal{NP}$-Hardness of Approximately Solving Linear Equations over Reals

Khot, Subhash, Moshkovitz, Dana
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 471 KB
english, 2013
9

Perfect Matchings in $O(n\log n)$ Time in Regular Bipartite Graphs

Goel, Ashish, Kapralov, Michael, Khanna, Sanjeev
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 228 KB
english, 2013
10

Graph Connectivities, Network Coding, and Expander Graphs

Cheung, Ho Yee, Lau, Lap Chi, Leung, Kai Man
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 392 KB
english, 2013
11

Branching-Time Model Checking of One-Counter Processes and Timed Automata

Göller, Stefan, Lohrey, Markus
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 760 KB
english, 2013
13

How to Compress Interactive Communication

Barak, Boaz, Braverman, Mark, Chen, Xi, Rao, Anup
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 470 KB
english, 2013
16

Efficient Edge Splitting-Off Algorithms Maintaining All-Pairs Edge-Connectivities

Lau, Lap Chi, Yung, Chun Kong
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 347 KB
english, 2013
17

On Multiplicative $\lambda$-Approximations and Some Geometric Applications

Newman, Ilan, Rabinovich, Yuri
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 414 KB
english, 2013
18

An Effective Dichotomy for the Counting Constraint Satisfaction Problem

Dyer, Martin, Richerby, David
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 392 KB
english, 2013
19

Locating Regions in a Sequence under Density Constraints

Burton, Benjamin A., Hiron, Mathias
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 328 KB
english, 2013
20

Determining Edge Expansion and Other Connectivity Measures of Graphs of Bounded Genus

Patel, Viresh
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 230 KB
english, 2013
21

Local List-Decoding and Testing of Random Linear Codes from High Error

Kopparty, Swastik, Saraf, Shubhangi
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 314 KB
english, 2013
23

Computing Shortest Paths amid Convex Pseudodisks

Chen, Danny Z., Hershberger, John, Wang, Haitao
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 903 KB
english, 2013
26

Pseudorandom Generators for Polynomial Threshold Functions

Meka, Raghu, Zuckerman, David
Journal:
SIAM Journal on Computing
Year:
2013
Language:
english
File:
PDF, 320 KB
english, 2013