@Preamble{
"\ifx \mathbb \undefined \def \mathbb #1{{\bf #1}} \fi"
}
@String{ack-nhfb = "Nelson H. F. Beebe,
University of Utah,
Department of Mathematics, 110 LCB
155 S 1400 E RM 233,
Salt Lake City, UT 84112-0090, USA,
Tel: +1 801 581 5254,
FAX: +1 801 581 4148,
e-mail: \path|beebe@math.utah.edu|,
\path|beebe@acm.org|,
\path|beebe@computer.org| (Internet),
URL: \path|http://www.math.utah.edu/~beebe/|"}
@String{pub-IEEE = "IEEE Computer Society Press"}
@String{pub-IEEE:adr = "1109 Spring Street, Suite 300,
Silver Spring, MD 20910, USA"}
@InProceedings{Bansal:2010:CAD,
author = "Nikhil Bansal",
title = "Constructive Algorithms for Discrepancy Minimization",
crossref = "IEEE:2010:PIA",
pages = "3--10",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.7",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Diakonikolas:2010:BIF,
author = "Ilias Diakonikolas and Daniel M. Kane and Jelani
Nelson",
title = "Bounded Independence Fools Degree-$2$ Threshold
Functions",
crossref = "IEEE:2010:PIA",
pages = "11--20",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.8",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Saxena:2010:SGC,
author = "Nitin Saxena and C. Seshadhri",
title = "From {Sylvester--Gallai} Configurations to Rank
Bounds: Improved Black-Box Identity Test for Depth-$3$
Circuits",
crossref = "IEEE:2010:PIA",
pages = "21--29",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.9",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Brody:2010:CPP,
author = "Joshua Brody and Elad Verbin",
title = "The Coin Problem and Pseudorandomness for Branching
Programs",
crossref = "IEEE:2010:PIA",
pages = "30--39",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.10",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Braverman:2010:PGR,
author = "Mark Braverman and Anup Rao and Ran Raz and Amir
Yehudayoff",
title = "Pseudorandom Generators for Regular Branching
Programs",
crossref = "IEEE:2010:PIA",
pages = "40--47",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.11",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Dwork:2010:BDP,
author = "Cynthia Dwork and Guy N. Rothblum and Salil Vadhan",
title = "Boosting and Differential Privacy",
crossref = "IEEE:2010:PIA",
pages = "51--60",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.12",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Hardt:2010:MWM,
author = "Moritz Hardt and Guy N. Rothblum",
title = "A Multiplicative Weights Mechanism for
Privacy-Preserving Data Analysis",
crossref = "IEEE:2010:PIA",
pages = "61--70",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.85",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Brenner:2010:IDP,
author = "Hai Brenner and Kobbi Nissim",
title = "Impossibility of Differentially Private Universally
Optimal Mechanisms",
crossref = "IEEE:2010:PIA",
pages = "71--80",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.13",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{McGregor:2010:LTP,
author = "Andrew McGregor and Ilya Mironov and Toniann Pitassi
and Omer Reingold and Kunal Talwar and Salil Vadhan",
title = "The Limits of Two-Party Differential Privacy",
crossref = "IEEE:2010:PIA",
pages = "81--90",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.14",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Moitra:2010:SPL,
author = "Ankur Moitra and Gregory Valiant",
title = "Settling the Polynomial Learnability of Mixtures of
{Gaussians}",
crossref = "IEEE:2010:PIA",
pages = "93--102",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.15",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Belkin:2010:PLD,
author = "Mikhail Belkin and Kaushik Sinha",
title = "Polynomial Learning of Distribution Families",
crossref = "IEEE:2010:PIA",
pages = "103--112",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.16",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Wimmer:2010:ALU,
author = "Karl Wimmer",
title = "Agnostically Learning under Permutation Invariant
Distributions",
crossref = "IEEE:2010:PIA",
pages = "113--122",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.17",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Vempala:2010:CRS,
author = "Santosh S. Vempala",
title = "Corrigendum: {A Random Sampling Algorithm for Learning
an Intersection of Halfspaces}",
crossref = "IEEE:2010:PIA",
pages = "123--123",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.18",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Vempala:2010:LCC,
author = "Santosh S. Vempala",
title = "Learning Convex Concepts from {Gaussian} Distributions
with {PCA}",
crossref = "IEEE:2010:PIA",
pages = "124--130",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.19",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Dvorak:2010:DFO,
author = "Zdenek Dvo{\v{r}}ak and Daniel Kra{\l} and Robin
Thomas",
title = "Deciding First-Order Properties for Sparse Graphs",
crossref = "IEEE:2010:PIA",
pages = "133--142",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.20",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Elberfeld:2010:LVT,
author = "Michael Elberfeld and Andreas Jakoby and Till Tantau",
title = "Logspace Versions of the Theorems of {Bodlaender} and
{Courcelle}",
crossref = "IEEE:2010:PIA",
pages = "143--152",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.21",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Kawarabayashi:2010:STM,
author = "Ken-ichi Kawarabayashi and Bruce Reed",
title = "A Separator Theorem in Minor-Closed Classes",
crossref = "IEEE:2010:PIA",
pages = "153--162",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.22",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Sidiropoulos:2010:OSP,
author = "Anastasios Sidiropoulos",
title = "Optimal Stochastic Planarization",
crossref = "IEEE:2010:PIA",
pages = "163--170",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.23",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Bjorklund:2010:DSU,
author = "Andreas Bj{\"o}rklund",
title = "Determinant Sums for Undirected {Hamiltonicity}",
crossref = "IEEE:2010:PIA",
pages = "173--182",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.24",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Santhanam:2010:FPN,
author = "Rahul Santhanam",
title = "Fighting Perebor: New and Improved Algorithms for
Formula and {QBF} Satisfiability",
crossref = "IEEE:2010:PIA",
pages = "183--192",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.25",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Rossman:2010:MCC,
author = "B. Rossman",
title = "The Monotone Complexity of $k$-clique on Random
Graphs",
crossref = "IEEE:2010:PIA",
pages = "193--201",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.26",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Rossman:2010:MCK,
author = "Benjamin Rossman",
title = "The Monotone Complexity of k-clique on Random Graphs",
crossref = "IEEE:2010:PIA",
pages = "193--201",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.26",
bibdate = "Tue Nov 6 07:45:16 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Viola:2010:CD,
author = "Emanuele Viola",
title = "The Complexity of Distributions",
crossref = "IEEE:2010:PIA",
pages = "202--211",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.27",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Dinur:2010:HFI,
author = "Irit Dinur and Subhash Khot and Will Perkins and Muli
Safra",
title = "Hardness of Finding Independent Sets in Almost
$3$-Colorable Graphs",
crossref = "IEEE:2010:PIA",
pages = "212--221",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.84",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Alon:2010:SLS,
author = "Noga Alon and Raphael Yuster",
title = "Solving Linear Systems through Nested Dissection",
crossref = "IEEE:2010:PIA",
pages = "225--234",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.28",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Koutis:2010:AOS,
author = "Ioannis Koutis and Gary L. Miller and Richard Peng",
title = "Approaching Optimality for Solving {SDD} Linear
Systems",
crossref = "IEEE:2010:PIA",
pages = "235--244",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.29",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Madry:2010:FAA,
author = "Aleksander Madry",
title = "Fast Approximation Algorithms for Cut-Based Problems
in Undirected Graphs",
crossref = "IEEE:2010:PIA",
pages = "245--254",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.30",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Makarychev:2010:MEO,
author = "Konstantin Makarychev and Yury Makarychev",
title = "Metric Extension Operators, Vertex Sparsifiers and
{Lipschitz} Extendability",
crossref = "IEEE:2010:PIA",
pages = "255--264",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.31",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Charikar:2010:VSA,
author = "Moses Charikar and Tom Leighton and Shi Li and Ankur
Moitra",
title = "Vertex Sparsifiers and Abstract Rounding Algorithms",
crossref = "IEEE:2010:PIA",
pages = "265--274",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.32",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Andrews:2010:AAE,
author = "Matthew Andrews",
title = "Approximation Algorithms for the Edge-Disjoint Paths
Problem via {Raecke} Decompositions",
crossref = "IEEE:2010:PIA",
pages = "277--286",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.33",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Sly:2010:CTU,
author = "Allan Sly",
title = "Computational Transition at the Uniqueness Threshold",
crossref = "IEEE:2010:PIA",
pages = "287--296",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.34",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Kumar:2010:CSN,
author = "Amit Kumar and Ravindran Kannan",
title = "Clustering with Spectral Norm and the $k$-Means
Algorithm",
crossref = "IEEE:2010:PIA",
pages = "299--308",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.35",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Awasthi:2010:SYP,
author = "Pranjal Awasthi and Avrim Blum and Or Sheffet",
title = "Stability Yields a {PTAS} for $k$-Median and $k$-Means
Clustering",
crossref = "IEEE:2010:PIA",
pages = "309--318",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.36",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Isaksson:2010:GMQ,
author = "Marcus Isaksson and Guy Kindler and Elchanan Mossel",
title = "The Geometry of Manipulation: a Quantitative Proof of
the {Gibbard--Satterthwaite} Theorem",
crossref = "IEEE:2010:PIA",
pages = "319--328",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.37",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Deshpande:2010:EVS,
author = "Amit Deshpande and Luis Rademacher",
title = "Efficient Volume Sampling for Row\slash Column Subset
Selection",
crossref = "IEEE:2010:PIA",
pages = "329--338",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.38",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Alon:2010:NLL,
author = "Noga Alon",
title = "A Non-linear Lower Bound for Planar Epsilon-Nets",
crossref = "IEEE:2010:PIA",
pages = "341--346",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.39",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Bosek:2010:SEU,
author = "Bartlomiej Bosek and Tomasz Krawczyk",
title = "The Sub-exponential Upper Bound for On-Line Chain
Partitioning",
crossref = "IEEE:2010:PIA",
pages = "347--354",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.40",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Rubin:2010:IBG,
author = "Natan Rubin and Haim Kaplan and Micha Sharir",
title = "Improved Bounds for Geometric Permutations",
crossref = "IEEE:2010:PIA",
pages = "355--364",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.41",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{DiBattista:2010:QNP,
author = "Giuseppe {Di Battista} and Fabrizio Frati and Janos
Pach",
title = "On the Queue Number of Planar Graphs",
crossref = "IEEE:2010:PIA",
pages = "365--374",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.42",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Andoni:2010:PAE,
author = "Alexandr Andoni and Robert Krauthgamer and Krzysztof
Onak",
title = "Polylogarithmic Approximation for Edit Distance and
the Asymmetric Query Complexity",
crossref = "IEEE:2010:PIA",
pages = "377--386",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.43",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Chakrabarti:2010:ICT,
author = "Amit Chakrabarti and Graham Cormode and Ranganath
Kondapally and Andrew McGregor",
title = "Information Cost Tradeoffs for Augmented Index and
Streaming Language Recognition",
crossref = "IEEE:2010:PIA",
pages = "387--396",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.44",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Haeupler:2010:NCA,
author = "Bernhard Haeupler and Barna Saha and Aravind
Srinivasan",
title = "New Constructive Aspects of the {Lov{\'a}sz} Local
Lemma",
crossref = "IEEE:2010:PIA",
pages = "397--406",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.45",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Bansal:2010:GS,
author = "Nikhil Bansal and Kirk Pruhs",
title = "The Geometry of Scheduling",
crossref = "IEEE:2010:PIA",
pages = "407--414",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.46",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Doty:2010:SFT,
author = "David Doty and Matthew J. Patitz and Dustin Reishus
and Robert T. Schweller and Scott M. Summers",
title = "Strong Fault-Tolerance for Self-Assembly with Fuzzy
Temperature",
crossref = "IEEE:2010:PIA",
pages = "417--426",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.47",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Cai:2010:HAM,
author = "Jin-Yi Cai and Pinyan Lu and Mingji Xia",
title = "Holographic Algorithms with Matchgates Capture
Precisely Tractable Planar{$_\#$CSP}",
crossref = "IEEE:2010:PIA",
pages = "427--436",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.48",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Cai:2010:DDT,
author = "Jin-Yi Cai and Xi Chen",
title = "A Decidable Dichotomy Theorem on Directed Graph
Homomorphisms with Non-negative Weights",
crossref = "IEEE:2010:PIA",
pages = "437--446",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.49",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Clarkson:2010:SOM,
author = "Kenneth L. Clarkson and Elad Hazan and David P.
Woodruff",
title = "Sublinear Optimization for Machine Learning",
crossref = "IEEE:2010:PIA",
pages = "449--457",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.50",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Saks:2010:ELI,
author = "Michael Saks and C. Seshadhri",
title = "Estimating the Longest Increasing Sequence in
Polylogarithmic Time",
crossref = "IEEE:2010:PIA",
pages = "458--467",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.51",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Tsur:2010:TPS,
author = "Gilad Tsur and Dana Ron",
title = "Testing Properties of Sparse Images",
crossref = "IEEE:2010:PIA",
pages = "468--477",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.52",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Bhattacharyya:2010:UFT,
author = "Arnab Bhattacharyya and Elena Grigorescu and Asaf
Shapira",
title = "A Unified Framework for Testing Linear-Invariant
Properties",
crossref = "IEEE:2010:PIA",
pages = "478--487",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.53",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Bhattacharyya:2010:OTR,
author = "Arnab Bhattacharyya and Swastik Kopparty and Grant
Schoenebeck and Madhu Sudan and David Zuckerman",
title = "Optimal Testing of {Reed--Muller} Codes",
crossref = "IEEE:2010:PIA",
pages = "488--497",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.54",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Brakerski:2010:OHB,
author = "Zvika Brakerski and Yael Tauman Kalai and Jonathan
Katz and Vinod Vaikuntanathan",
title = "Overcoming the Hole in the Bucket: Public-Key
Cryptography Resilient to Continual Memory Leakage",
crossref = "IEEE:2010:PIA",
pages = "501--510",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.55",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Dodis:2010:CAC,
author = "Yevgeniy Dodis and Kristiyan Haralambiev and Adriana
Lopez-Alt and Daniel Wichs",
title = "Cryptography against Continuous Memory Attacks",
crossref = "IEEE:2010:PIA",
pages = "511--520",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.56",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Lewko:2010:IPR,
author = "Allison Lewko and Brent Waters",
title = "On the Insecurity of Parallel Repetition for Leakage
Resilience",
crossref = "IEEE:2010:PIA",
pages = "521--530",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.57",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Wee:2010:BBR,
author = "Hoeteck Wee",
title = "Black-Box, Round-Efficient Secure Computation via
Non-malleability Amplification",
crossref = "IEEE:2010:PIA",
pages = "531--540",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.87",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Canetti:2010:AHC,
author = "Ran Canetti and Huijia Lin and Rafael Pass",
title = "Adaptive Hardness and Composable Security in the Plain
Model from Standard Assumptions",
crossref = "IEEE:2010:PIA",
pages = "541--550",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.86",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Potechin:2010:BMS,
author = "Aaron Potechin",
title = "Bounds on Monotone Switching Networks for Directed
Connectivity",
crossref = "IEEE:2010:PIA",
pages = "553--562",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.58",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Arora:2010:SAU,
author = "Sanjeev Arora and Boaz Barak and David Steurer",
title = "Subexponential Algorithms for Unique Games and Related
Problems",
crossref = "IEEE:2010:PIA",
pages = "563--572",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.59",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Chekuri:2010:DRR,
author = "Chandra Chekuri and Jan Vondrak and Rico Zenklusen",
title = "Dependent Randomized Rounding via Exchange Properties
of Combinatorial Structures",
crossref = "IEEE:2010:PIA",
pages = "575--584",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.60",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Andrews:2010:MCN,
author = "Matthew Andrews and Spyridon Antonakopoulos and Lisa
Zhang",
title = "Minimum-Cost Network Design with (Dis)economies of
Scale",
crossref = "IEEE:2010:PIA",
pages = "585--592",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.61",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Goel:2010:OTS,
author = "Ashish Goel and Ian Post",
title = "One Tree Suffices: a Simultaneous {O}(1)-Approximation
for Single-Sink Buy-at-Bulk",
crossref = "IEEE:2010:PIA",
pages = "593--600",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.62",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Borradaile:2010:MSC,
author = "Glencora Borradaile and Piotr Sankowski and Christian
Wulff-Nilsen",
title = "Min $st$-cut Oracle for Planar Graphs with Near-Linear
Preprocessing Time",
crossref = "IEEE:2010:PIA",
pages = "601--610",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.63",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Maji:2010:CCC,
author = "Hemanta K. Maji and Manoj Prabhakaran and Amit Sahai",
title = "On the Computational Complexity of Coin Flipping",
crossref = "IEEE:2010:PIA",
pages = "613--622",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.64",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Gradwohl:2010:SRC,
author = "Ronen Gradwohl and Noam Livne and Alon Rosen",
title = "Sequential Rationality in Cryptographic Protocols",
crossref = "IEEE:2010:PIA",
pages = "623--632",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.65",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Harrow:2010:ETP,
author = "Aram W. Harrow and Ashley Montanaro",
title = "An Efficient Test for Product States with Applications
to Quantum {Merlin--Arthur} Games",
crossref = "IEEE:2010:PIA",
pages = "633--642",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.66",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Williams:2010:SEB,
author = "Virginia Vassilevska Williams and Ryan Williams",
title = "Subcubic Equivalences between Path, Matrix and
Triangle Problems",
crossref = "IEEE:2010:PIA",
pages = "645--654",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.67",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Weimann:2010:RPF,
author = "Oren Weimann and Raphael Yuster",
title = "Replacement Paths via Fast Matrix Multiplication",
crossref = "IEEE:2010:PIA",
pages = "655--662",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.68",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Peres:2010:APS,
author = "Yuval Peres and Dmitry Sotnikov and Benny Sudakov and
Uri Zwick",
title = "All-Pairs Shortest Paths in {$O(n^2)$} Time with High
Probability",
crossref = "IEEE:2010:PIA",
pages = "663--672",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.69",
bibdate = "Thu Apr 12 09:34:19 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Duan:2010:AMW,
author = "Ran Duan and Seth Pettie",
title = "Approximating Maximum Weight Matching in Near-Linear
Time",
crossref = "IEEE:2010:PIA",
pages = "673--682",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.70",
bibdate = "Thu Apr 12 09:34:19 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Gopalan:2010:FAA,
author = "Parikshit Gopalan",
title = "A {Fourier}-Analytic Approach to {Reed--Muller}
Decoding",
crossref = "IEEE:2010:PIA",
pages = "685--694",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.71",
bibdate = "Thu Apr 12 09:34:19 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Lovett:2010:PGC,
author = "Shachar Lovett and Partha Mukhopadhyay and Amir
Shpilka",
title = "Pseudorandom Generators for {CC0}[$p$] and the
{Fourier} Spectrum of Low-Degree Polynomials over
Finite Fields",
crossref = "IEEE:2010:PIA",
pages = "695--704",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.72",
bibdate = "Thu Apr 12 09:34:19 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Dvir:2010:MVC,
author = "Zeev Dvir and Parikshit Gopalan and Sergey Yekhanin",
title = "Matching Vector Codes",
crossref = "IEEE:2010:PIA",
pages = "705--714",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.73",
bibdate = "Thu Apr 12 09:34:19 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Ben-Aroya:2010:LLD,
author = "Avraham Ben-Aroya and Klim Efremenko and Amnon
Ta-Shma",
title = "Local List Decoding with a Constant Number of
Queries",
crossref = "IEEE:2010:PIA",
pages = "715--722",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.88",
bibdate = "Thu Apr 12 09:34:19 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Guruswami:2010:CCS,
author = "Venkatesan Guruswami and Adam Smith",
title = "Codes for Computationally Simple Channels: Explicit
Constructions with Optimal Rate",
crossref = "IEEE:2010:PIA",
pages = "723--732",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.74",
bibdate = "Thu Apr 12 09:34:19 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Leme:2010:PBN,
author = "Renato Paes Leme and Eva Tardos",
title = "Pure and {Bayes--Nash} Price of Anarchy for
Generalized Second Price Auction",
crossref = "IEEE:2010:PIA",
pages = "735--744",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.75",
bibdate = "Thu Apr 12 09:34:19 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Kempe:2010:FTA,
author = "David Kempe and Mahyar Salek and Cristopher Moore",
title = "Frugal and Truthful Auctions for Vertex Covers, Flows
and Cuts",
crossref = "IEEE:2010:PIA",
pages = "745--754",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.76",
bibdate = "Thu Apr 12 09:34:19 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Chen:2010:FMD,
author = "Ning Chen and Edith Elkind and Nick Gravin and Fedor
Petrov",
title = "Frugal Mechanism Design via Spectral Techniques",
crossref = "IEEE:2010:PIA",
pages = "755--764",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.77",
bibdate = "Thu Apr 12 09:34:19 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Singer:2010:BFM,
author = "Yaron Singer",
title = "Budget Feasible Mechanisms",
crossref = "IEEE:2010:PIA",
pages = "765--774",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.78",
bibdate = "Thu Apr 12 09:34:19 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Dughmi:2010:BBR,
author = "Shaddin Dughmi and Tim Roughgarden",
title = "Black-Box Randomized Reductions in Algorithmic
Mechanism Design",
crossref = "IEEE:2010:PIA",
pages = "775--784",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.79",
bibdate = "Thu Apr 12 09:34:19 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Arbitman:2010:BCH,
author = "Yuriy Arbitman and Moni Naor and Gil Segev",
title = "Backyard Cuckoo Hashing: Constant Worst-Case
Operations with a Succinct Representation",
crossref = "IEEE:2010:PIA",
pages = "787--796",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.80",
bibdate = "Thu Apr 12 09:34:19 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Lovett:2010:LBD,
author = "Shachar Lovett and Ely Porat",
title = "A Lower Bound for Dynamic Approximate Membership Data
Structures",
crossref = "IEEE:2010:PIA",
pages = "797--804",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.81",
bibdate = "Thu Apr 12 09:34:19 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Panigrahy:2010:LBN,
author = "Rina Panigrahy and Kunal Talwar and Udi Wieder",
title = "Lower Bounds on Near Neighbor Search via Metric
Expansion",
crossref = "IEEE:2010:PIA",
pages = "805--814",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.82",
bibdate = "Thu Apr 12 09:34:19 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Patrascu:2010:DOB,
author = "Mihai Patrascu and Liam Roditty",
title = "Distance Oracles beyond the {Thorup--Zwick} Bound",
crossref = "IEEE:2010:PIA",
pages = "815--823",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.83",
bibdate = "Thu Apr 12 09:34:19 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Anonymous:2010:AI,
author = "Anonymous",
title = "Author index",
crossref = "IEEE:2010:PIA",
pages = "824--826",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.90",
bibdate = "Thu Apr 12 09:34:19 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Anonymous:2010:RP,
author = "Anonymous",
title = "Roster Page",
crossref = "IEEE:2010:PIA",
pages = "828--828",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.91",
bibdate = "Thu Apr 12 09:34:19 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Anonymous:2010:CA,
author = "Anonymous",
title = "Cover Art",
crossref = "IEEE:2010:PIA",
pages = "C1--C1",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.94",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Anonymous:2010:CP,
author = "Anonymous",
title = "Copyright Page",
crossref = "IEEE:2010:PIA",
pages = "iv--iv",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.3",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Anonymous:2010:F,
author = "Anonymous",
title = "Foreword",
crossref = "IEEE:2010:PIA",
pages = "xii--xii",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.5",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Anonymous:2010:OC,
author = "Anonymous",
title = "Organizing Committee",
crossref = "IEEE:2010:PIA",
pages = "xiii--xiii",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.92",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Anonymous:2010:PC,
author = "Anonymous",
title = "Program Committee",
crossref = "IEEE:2010:PIA",
pages = "xiv--xiv",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.93",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Anonymous:2010:R,
author = "Anonymous",
title = "Reviewers",
crossref = "IEEE:2010:PIA",
pages = "xv--xvi",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.6",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Anonymous:2010:TC,
author = "Anonymous",
title = "Table of Contents",
crossref = "IEEE:2010:PIA",
pages = "v--x",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.4",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Anonymous:2010:TP,
author = "Anonymous",
title = "Title Page i",
crossref = "IEEE:2010:PIA",
pages = "i--i",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.1",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Anonymous:2010:TPI,
author = "Anonymous",
title = "Title Page iii",
crossref = "IEEE:2010:PIA",
pages = "iii--iii",
year = "2010",
DOI = "https://doi.org/10.1109/FOCS.2010.2",
bibdate = "Thu Apr 12 09:34:12 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376",
}
@InProceedings{Dwork:2011:PDP,
author = "Cynthia Dwork",
title = "The Promise of Differential Privacy: a Tutorial on
Algorithmic Techniques",
crossref = "IEEE:2011:PIA",
pages = "1--2",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.88",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Pruhs:2011:GCA,
author = "Kirk Pruhs",
title = "{Green} Computing Algorithmics",
crossref = "IEEE:2011:PIA",
pages = "3--4",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.44",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Vaikuntanathan:2011:CBN,
author = "Vinod Vaikuntanathan",
title = "Computing Blindfolded: New Developments in Fully
Homomorphic Encryption",
crossref = "IEEE:2011:PIA",
pages = "5--16",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.98",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Bansal:2011:MMG,
author = "Nikhil Bansal and Uriel Feige and Robert Krauthgamer
and Konstantin Makarychev and Viswanath Nagarajan and
Joseph (Seffi) Naor and Roy Schwartz",
title = "Min-max Graph Partitioning and Small Set Expansion",
crossref = "IEEE:2011:PIA",
pages = "17--26",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.79",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Kawarabayashi:2011:GMA,
author = "Ken-ichi Kawarabayashi and Bruce Reed and Paul
Wollan",
title = "The Graph Minor Algorithm with Parity Conditions",
crossref = "IEEE:2011:PIA",
pages = "27--36",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.52",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Wulff-Nilsen:2011:STM,
author = "Christian Wulff-Nilsen",
title = "Separator Theorems for Minor-Free and Shallow
Minor-Free Graphs with Applications",
crossref = "IEEE:2011:PIA",
pages = "37--46",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.15",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Bonsma:2011:CFA,
author = "Paul Bonsma and Jens Schulz and Andreas Wiese",
title = "A Constant Factor Approximation Algorithm for
Unsplittable Flow on Paths",
crossref = "IEEE:2011:PIA",
pages = "47--56",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.10",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Bindel:2011:HBF,
author = "David Bindel and Jon Kleinberg and Sigal Oren",
title = "How Bad is Forming Your Own Opinion?",
crossref = "IEEE:2011:PIA",
pages = "57--66",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.43",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Goldberg:2011:CHM,
author = "Paul W. Goldberg and Christos H. Papadimitriou and
Rahul Savani",
title = "The Complexity of the Homotopy Method, Equilibrium
Selection, and {Lemke--Howson} Solutions",
crossref = "IEEE:2011:PIA",
pages = "67--76",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.26",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Blum:2011:WPM,
author = "Avrim Blum and Anupam Gupta and Yishay Mansour and
Ankit Sharma",
title = "Welfare and Profit Maximization with Production
Costs",
crossref = "IEEE:2011:PIA",
pages = "77--86",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.68",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Chen:2011:MDS,
author = "Jing Chen and Silvio Micali",
title = "Mechanism Design with Set-Theoretic Beliefs",
crossref = "IEEE:2011:PIA",
pages = "87--96",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.11",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Brakerski:2011:EFH,
author = "Zvika Brakerski and Vinod Vaikuntanathan",
title = "Efficient Fully Homomorphic Encryption from (Standard)
{LWE}",
crossref = "IEEE:2011:PIA",
pages = "97--106",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.12",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Gentry:2011:FHE,
author = "Craig Gentry and Shai Halevi",
title = "Fully Homomorphic Encryption without Squashing Using
Depth-$3$ Arithmetic Circuits",
crossref = "IEEE:2011:PIA",
pages = "107--109",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.94",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Haitner:2011:CFC,
author = "Iftach Haitner and Eran Omri",
title = "Coin Flipping with Constant Bias Implies One-Way
Functions",
crossref = "IEEE:2011:PIA",
pages = "110--119",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.29",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Applebaum:2011:HGA,
author = "Benny Applebaum and Yuval Ishai and Eyal Kushilevitz",
title = "How to Garble Arithmetic Circuits",
crossref = "IEEE:2011:PIA",
pages = "120--129",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.40",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Caputo:2011:SMT,
author = "Pietro Caputo and Fabio Martinelli and Fabio Lucio
Toninelli",
title = "Sharp Mixing Time Bounds for Sampling Random
Surfaces",
crossref = "IEEE:2011:PIA",
pages = "130--139",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.47",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Restrepo:2011:IMC,
author = "Ricardo Restrepo and Jinwoo Shin and Prasad Tetali and
Eric Vigoda and Linji Yang",
title = "Improved Mixing Condition on the Grid for Counting and
Sampling Independent Sets",
crossref = "IEEE:2011:PIA",
pages = "140--149",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.45",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Cygan:2011:SCP,
author = "Marek Cygan and Jesper Nederlof and Marcin Pilipczuk
and Michal Pilipczuk and Joham M. M. van Rooij and
Jakub Onufry Wojtaszczyk",
title = "Solving Connectivity Problems Parameterized by
Treewidth in Single Exponential Time",
crossref = "IEEE:2011:PIA",
pages = "150--159",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.23",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Kawarabayashi:2011:MKW,
author = "Ken-ichi Kawarabayashi and Mikkel Thorup",
title = "The Minimum k-way Cut of Bounded Size is
Fixed-Parameter Tractable",
crossref = "IEEE:2011:PIA",
pages = "160--169",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.53",
ISSN = "0272-5428",
bibdate = "Tue Nov 6 07:45:16 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Kawarabayashi:2011:MWC,
author = "K. Kawarabayashi and M. Thorup",
title = "The Minimum $k$-way Cut of Bounded Size is
Fixed-Parameter Tractable",
crossref = "IEEE:2011:PIA",
pages = "160--169",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.53",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Borradaile:2011:MSM,
author = "Glencora Borradaile and Philip N. Klein and Shay Mozes
and Yahav Nussbaum and Christian Wulff-Nilsen",
title = "Multiple-Source Multiple-Sink Maximum Flow in Directed
Planar Graphs in Near-Linear Time",
crossref = "IEEE:2011:PIA",
pages = "170--179",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.73",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Roditty:2011:MWC,
author = "Liam Roditty and Virginia Vassilevska Williams",
title = "Minimum Weight Cycles and Triangles: Equivalences and
Algorithms",
crossref = "IEEE:2011:PIA",
pages = "180--189",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.27",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Cheung:2011:GCN,
author = "Ho Yee Cheung and Lap Chi Lau and Kai Man Leung",
title = "Graph Connectivities, Network Coding, and Expander
Graphs",
crossref = "IEEE:2011:PIA",
pages = "190--199",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.55",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Seguin-Charbonneau:2011:MED,
author = "Loic Seguin-Charbonneau and F. Bruce Shepherd",
title = "Maximum Edge-Disjoint Paths in Planar Graphs with
Congestion $2$",
crossref = "IEEE:2011:PIA",
pages = "200--209",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.30",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Naor:2011:ONW,
author = "Joseph (Seffi) Naor and Debmalya Panigrahi and Mohit
Singh",
title = "Online Node-Weighted {Steiner} Tree and Related
Problems",
crossref = "IEEE:2011:PIA",
pages = "210--219",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.65",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Viola:2011:ECS,
author = "Emanuele Viola",
title = "Extractors for Circuit Sources",
crossref = "IEEE:2011:PIA",
pages = "220--229",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.20",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Viola:2011:RBD,
author = "Emanuele Viola",
title = "Randomness Buys Depth for Approximate Counting",
crossref = "IEEE:2011:PIA",
pages = "230--239",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.19",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Bogdanov:2011:PRO,
author = "Andrej Bogdanov and Periklis A. Papakonstaninou and
Andrew Wan",
title = "Pseudorandomness for Read-Once Formulas",
crossref = "IEEE:2011:PIA",
pages = "240--246",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.57",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Shaltiel:2011:DAS,
author = "Ronen Shaltiel",
title = "Dispersers for Affine Sources with Sub-polynomial
Entropy",
crossref = "IEEE:2011:PIA",
pages = "247--256",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.37",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Kane:2011:SPP,
author = "Daniel M. Kane",
title = "A Small {PRG} for Polynomial Threshold Functions of
{Gaussians}",
crossref = "IEEE:2011:PIA",
pages = "257--266",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.16",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Bansal:2011:PCA,
author = "Nikhil Bansal and Niv Buchbinder and Aleksander Madry
and Joseph (Seffi) Naor",
title = "A Polylogarithmic-Competitive Algorithm for the
$k$-Server Problem",
crossref = "IEEE:2011:PIA",
pages = "267--276",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.63",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Hertli:2011:SFS,
author = "Timon Hertli",
title = "{$3$-SAT} Faster and Simpler --- Unique-{SAT} Bounds
for {PPSZ} Hold in General",
crossref = "IEEE:2011:PIA",
pages = "277--284",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.22",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Indyk:2011:PAS,
author = "Piotr Indyk and Eric Price and David P. Woodruff",
title = "On the Power of Adaptivity in Sparse Recovery",
crossref = "IEEE:2011:PIA",
pages = "285--294",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.83",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Price:2011:ASR,
author = "E. Price and D. P. Woodruff",
title = "$(1 + \epsilon)$-Approximate Sparse Recovery",
crossref = "IEEE:2011:PIA",
pages = "295--304",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.92",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Price:2011:EAS,
author = "Eric Price and David P. Woodruff",
title = "(1 + eps)-Approximate Sparse Recovery",
crossref = "IEEE:2011:PIA",
pages = "295--304",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.92",
ISSN = "0272-5428",
bibdate = "Tue Nov 6 07:45:16 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Boutsidis:2011:NOC,
author = "Christos Boutsidis and Petros Drineas and Malik
Magdon-Ismail",
title = "Near Optimal Column-Based Matrix Reconstruction",
crossref = "IEEE:2011:PIA",
pages = "305--314",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.21",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Andoni:2011:NLL,
author = "Alexandr Andoni and Moses S. Charikar and Ofer Neiman
and Huy L. Nguyen",
title = "Near Linear Lower Bound for Dimension Reduction in
{L1}",
crossref = "IEEE:2011:PIA",
pages = "315--323",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.87",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Aharonov:2011:ALC,
author = "Dorit Aharonov and Itai Arad and Zeph Landau and Umesh
Vazirani",
title = "The {$1$D} Area Law and the Complexity of Quantum
States: a Combinatorial Approach",
crossref = "IEEE:2011:PIA",
pages = "324--333",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.91",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Aharonov:2011:CCL,
author = "Dorit Aharonov and Lior Eldar",
title = "On the Complexity of Commuting Local Hamiltonians, and
Tight Conditions for Topological Order in Such
Systems",
crossref = "IEEE:2011:PIA",
pages = "334--343",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.58",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Lee:2011:QQC,
author = "Troy Lee and Rajat Mittal and Ben W. Reichardt and
Robert Spalek and Mario Szegedy",
title = "Quantum Query Complexity of State Conversion",
crossref = "IEEE:2011:PIA",
pages = "344--353",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.75",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Chailloux:2011:OBQ,
author = "Andre Chailloux and Iordanis Kerenidis",
title = "Optimal Bounds for Quantum Bit Commitment",
crossref = "IEEE:2011:PIA",
pages = "354--362",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.42",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Andoni:2011:SAP,
author = "Alexandr Andoni and Robert Krauthgamer and Krzysztof
Onak",
title = "Streaming Algorithms via Precision Sampling",
crossref = "IEEE:2011:PIA",
pages = "363--372",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.82",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Elkin:2011:SSL,
author = "Michael Elkin and Shay Solomon",
title = "{Steiner} Shallow-Light Trees are Exponentially
Lighter than Spanning Ones",
crossref = "IEEE:2011:PIA",
pages = "373--382",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.18",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Baswana:2011:FDM,
author = "Surender Baswana and Manoj Gupta and Sandeep Sen",
title = "Fully Dynamic Maximal Matching in {$O(\log n)$} Update
Time",
crossref = "IEEE:2011:PIA",
pages = "383--392",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.89",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Blume:2011:WNL,
author = "Lawrence Blume and David Easley and Jon Kleinberg and
Robert Kleinberg and Eva Tardos",
title = "Which Networks are Least Susceptible to Cascading
Failures?",
crossref = "IEEE:2011:PIA",
pages = "393--402",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.38",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Valiant:2011:PLE,
author = "Gregory Valiant and Paul Valiant",
title = "The Power of Linear Estimators",
crossref = "IEEE:2011:PIA",
pages = "403--412",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.81",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Falik:2011:APR,
author = "Dvir Falik and Ehud Friedgut",
title = "An Algebraic Proof of a Robust Social Choice
Impossibility Theorem",
crossref = "IEEE:2011:PIA",
pages = "413--422",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.72",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Czumaj:2011:PGR,
author = "Artur Czumaj and Morteza Monemizadeh and Krzysztof
Onak and Christian Sohler",
title = "Planar Graphs: Random Walks and Bipartiteness
Testing",
crossref = "IEEE:2011:PIA",
pages = "423--432",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.69",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Jha:2011:TRL,
author = "Madhav Jha and Sofya Raskhodnikova",
title = "Testing and Reconstruction of {Lipschitz} Functions
with Applications to Data Privacy",
crossref = "IEEE:2011:PIA",
pages = "433--442",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.13",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Kolla:2011:HPU,
author = "Alexandra Kolla and Konstantin Makarychev and Yury
Makarychev",
title = "How to Play Unique Games Against a Semi-random
Adversary: Study of Semi-random Models of Unique
Games",
crossref = "IEEE:2011:PIA",
pages = "443--452",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.78",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Braverman:2011:GCS,
author = "Mark Braverman and Konstantin Makarychev and Yury
Makarychev and Assaf Naor",
title = "The {Grothendieck} Constant is Strictly Smaller than
{Krivine}'s Bound",
crossref = "IEEE:2011:PIA",
pages = "453--462",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.77",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Jain:2011:PAA,
author = "Rahul Jain and Penghui Yao",
title = "A Parallel Approximation Algorithm for Positive
Semidefinite Programming",
crossref = "IEEE:2011:PIA",
pages = "463--471",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.25",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Barak:2011:RSP,
author = "Boaz Barak and Prasad Raghavendra and David Steurer",
title = "Rounding Semidefinite Programming Hierarchies via
Global Correlation",
crossref = "IEEE:2011:PIA",
pages = "472--481",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.95",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Guruswami:2011:LHH,
author = "Venkatesan Guruswami and Ali Kemal Sinop",
title = "{Lasserre} Hierarchy, Higher Eigenvalues, and
Approximation Schemes for Graph Partitioning and
Quadratic Integer Programming with {PSD} Objectives",
crossref = "IEEE:2011:PIA",
pages = "482--491",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.36",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Chierichetti:2011:ML,
author = "Flavio Chierichetti and Ravi Kumar and Prabhakar
Raghavan",
title = "{Markov} Layout",
crossref = "IEEE:2011:PIA",
pages = "492--501",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.71",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Dughmi:2011:LRM,
author = "Shaddin Dughmi and Jan Vondr{\'a}k",
title = "Limitations of Randomized Mechanisms for Combinatorial
Auctions",
crossref = "IEEE:2011:PIA",
pages = "502--511",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.64",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Alaei:2011:BCA,
author = "Saeed Alaei",
title = "{Bayesian} Combinatorial Auctions: Expanding Single
Buyer Mechanisms to Many Buyers",
crossref = "IEEE:2011:PIA",
pages = "512--521",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.90",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Cai:2011:EVT,
author = "Yang Cai and Constantinos Daskalakis",
title = "Extreme-Value Theorems for Optimal Multidimensional
Pricing",
crossref = "IEEE:2011:PIA",
pages = "522--531",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.76",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Caragiannis:2011:ECA,
author = "Ioannis Caragiannis and Angelo Fanelli and Nick Gravin
and Alexander Skopalik",
title = "Efficient Computation of Approximate Pure {Nash}
Equilibria in Congestion Games",
crossref = "IEEE:2011:PIA",
pages = "532--541",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.50",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Larsen:2011:RSG,
author = "Kasper Green Larsen",
title = "On Range Searching in the Group Model and
Combinatorial Discrepancy",
crossref = "IEEE:2011:PIA",
pages = "542--549",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.14",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Gharan:2011:RRA,
author = "Shayan Oveis Gharan and Amin Saberi and Mohit Singh",
title = "A Randomized Rounding Approach to the Traveling
Salesman Problem",
crossref = "IEEE:2011:PIA",
pages = "550--559",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.80",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Moemke:2011:AGT,
author = "Tobias Moemke and Ola Svensson",
title = "Approximating Graphic {TSP} by Matchings",
crossref = "IEEE:2011:PIA",
pages = "560--569",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.56",
ISSN = "0272-5428",
bibdate = "Tue Nov 6 07:45:16 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Momke:2011:AGT,
author = "T. Momke and O. Svensson",
title = "Approximating Graphic {TSP} by Matchings",
crossref = "IEEE:2011:PIA",
pages = "560--569",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.56",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Feldman:2011:UCG,
author = "Moran Feldman and Joseph (Seffi) Naor and Roy
Schwartz",
title = "A Unified Continuous Greedy Algorithm for Submodular
Maximization",
crossref = "IEEE:2011:PIA",
pages = "570--579",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.46",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Dadush:2011:ELA,
author = "Daniel Dadush and Chris Peikert and Santosh Vempala",
title = "Enumerative Lattice Algorithms in any Norm Via
{$M$}-ellipsoid Coverings",
crossref = "IEEE:2011:PIA",
pages = "580--589",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.31",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Koutis:2011:NML,
author = "Ioannis Koutis and Gary L. Miller and Richard Peng",
title = "A Nearly-$m \log n$ Time Solver for {SDD} Linear
Systems",
crossref = "IEEE:2011:PIA",
pages = "590--598",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.85",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Celis:2011:BBS,
author = "L. Elisa Celis and Omer Reingold and Gil Segev and Udi
Wieder",
title = "Balls and Bins: Smaller Hash Families and Faster
Evaluation",
crossref = "IEEE:2011:PIA",
pages = "599--608",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.49",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Blasiak:2011:LPP,
author = "Anna Blasiak and Robert Kleinberg and Eyal Lubetzky",
title = "Lexicographic Products and the Power of Non-linear
Network Coding",
crossref = "IEEE:2011:PIA",
pages = "609--618",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.39",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Tulsiani:2011:QGL,
author = "Madhur Tulsiani and Julia Wolf",
title = "Quadratic {Goldreich--Levin} Theorems",
crossref = "IEEE:2011:PIA",
pages = "619--628",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.59",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:29 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Haramaty:2011:OTM,
author = "Elad Haramaty and Amir Shpilka and Madhu Sudan",
title = "Optimal Testing of Multivariate Polynomials over Small
Prime Fields",
crossref = "IEEE:2011:PIA",
pages = "629--637",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.61",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:29 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Bhattacharyya:2011:TLB,
author = "Arnab Bhattacharyya and Zeev Dvir and Amir Shpilka and
Shubhangi Saraf",
title = "Tight Lower Bounds for $2$-query {LCCs} over Finite
Fields",
crossref = "IEEE:2011:PIA",
pages = "638--647",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.28",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:29 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Khot:2011:TPO,
author = "Subhash Khot and Muli Safra",
title = "A Two Prover One Round Game with Strong Soundness",
crossref = "IEEE:2011:PIA",
pages = "648--657",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.62",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:29 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Chung:2011:RCP,
author = "Kai-Min Chung and Rafael Pass",
title = "The Randomness Complexity of Parallel Repetition",
crossref = "IEEE:2011:PIA",
pages = "658--667",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.93",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:29 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Dodis:2011:PAN,
author = "Yevgeniy Dodis and Xin Li and Trevor D. Wooley and
David Zuckerman",
title = "Privacy Amplification and Non-malleable Extractors via
Character Sums",
crossref = "IEEE:2011:PIA",
pages = "668--677",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.67",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:29 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Goyal:2011:SCP,
author = "Vipul Goyal and Hemanta K. Maji",
title = "Stateless Cryptographic Protocols",
crossref = "IEEE:2011:PIA",
pages = "678--687",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.74",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:29 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Dodis:2011:SSC,
author = "Yevgeniy Dodis and Allison Lewko and Brent Waters and
Daniel Wichs",
title = "Storing Secrets on Continually Leaky Devices",
crossref = "IEEE:2011:PIA",
pages = "688--697",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.35",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:29 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Shah:2011:MAU,
author = "Devavrat Shah and Jinwoo Shin and Prasad Tetali",
title = "Medium Access Using Queues",
crossref = "IEEE:2011:PIA",
pages = "698--707",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.99",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:29 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Fraigniaud:2011:LDD,
author = "Pierre Fraigniaud and Amos Korman and David Peleg",
title = "Local Distributed Decision",
crossref = "IEEE:2011:PIA",
pages = "708--717",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.17",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:29 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Alistarh:2011:CR,
author = "Dan Alistarh and James Aspnes and Seth Gilbert and
Rachid Guerraoui",
title = "The Complexity of Renaming",
crossref = "IEEE:2011:PIA",
pages = "718--727",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.66",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:29 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Bender:2011:MEL,
author = "Michael A. Bender and Seth Gilbert",
title = "Mutual Exclusion with {$O(\log^2 \log n)$} Amortized
Work",
crossref = "IEEE:2011:PIA",
pages = "728--737",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.84",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:29 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Huang:2011:AGS,
author = "Zhiyi Huang and Sampath Kannan and Sanjeev Khanna",
title = "Algorithms for the Generalized Sorting Problem",
crossref = "IEEE:2011:PIA",
pages = "738--747",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.54",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:29 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Braverman:2011:IEA,
author = "Mark Braverman and Anup Rao",
title = "Information Equals Amortized Communication",
crossref = "IEEE:2011:PIA",
pages = "748--757",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.86",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:29 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Khanna:2011:DCC,
author = "Sanjeev Khanna and Madhu Sudan",
title = "Delays and the Capacity of Continuous-Time Channels",
crossref = "IEEE:2011:PIA",
pages = "758--767",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.60",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:29 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Gelles:2011:EEC,
author = "Ran Gelles and Ankur Moitra and Amit Sahai",
title = "Efficient and Explicit Coding for Interactive
Communication",
crossref = "IEEE:2011:PIA",
pages = "768--777",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.51",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:29 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Gupta:2011:ERR,
author = "Ankit Gupta and Neeraj Kayal and Satya Lokam",
title = "Efficient Reconstruction of Random Multilinear
Formulas",
crossref = "IEEE:2011:PIA",
pages = "778--787",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.70",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:29 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Kaufman:2011:NEW,
author = "Tali Kaufman and Shachar Lovett",
title = "New Extension of the {Weil} Bound for Character Sums
with Applications to Coding",
crossref = "IEEE:2011:PIA",
pages = "788--796",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.41",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:29 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Li:2011:MEU,
author = "Jian Li and Amol Deshpande",
title = "Maximizing Expected Utility for Stochastic
Combinatorial Optimization Problems",
crossref = "IEEE:2011:PIA",
pages = "797--806",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.33",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:29 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Chekuri:2011:AAS,
author = "Chandra Chekuri and Alina Ene",
title = "Approximation Algorithms for Submodular Multiway
Partition",
crossref = "IEEE:2011:PIA",
pages = "807--816",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.34",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:29 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Gopalan:2011:FKR,
author = "Parikshit Gopalan and Adam Klivans and Raghu Meka and
Daniel Stefankovic and Santosh Vempala and Eric
Vigoda",
title = "An {FPTAS} for \#Knapsack and Related Counting
Problems",
crossref = "IEEE:2011:PIA",
pages = "817--826",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.32",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:29 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Gupta:2011:AAC,
author = "Anupam Gupta and Ravishankar Krishnaswamy and Marco
Molinaro and R. Ravi",
title = "Approximation Algorithms for Correlated Knapsacks and
Non-martingale Bandits",
crossref = "IEEE:2011:PIA",
pages = "827--836",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.48",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:29 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Kanade:2011:ER,
author = "Varun Kanade",
title = "Evolution with Recombination",
crossref = "IEEE:2011:PIA",
pages = "837--846",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.24",
ISSN = "0272-5428",
bibdate = "Thu Apr 12 09:34:29 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Anonymous:2011:AI,
author = "Anonymous",
title = "Author index",
crossref = "IEEE:2011:PIA",
pages = "847--849",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.96",
bibdate = "Thu Apr 12 09:34:29 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Anonymous:2011:PI,
author = "Anonymous",
title = "{Publisher}'s Information",
crossref = "IEEE:2011:PIA",
pages = "850--850",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.97",
bibdate = "Thu Apr 12 09:34:29 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Anonymous:2011:A,
author = "Anonymous",
title = "Awards",
crossref = "IEEE:2011:PIA",
pages = "xvii--xvii",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.8",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Anonymous:2011:CA,
author = "Anonymous",
title = "Cover Art",
crossref = "IEEE:2011:PIA",
pages = "C1--C1",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.100",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Anonymous:2011:CP,
author = "Anonymous",
title = "Copyright Page",
crossref = "IEEE:2011:PIA",
pages = "iv--iv",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.3",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Anonymous:2011:F,
author = "Anonymous",
title = "Foreword",
crossref = "IEEE:2011:PIA",
pages = "xii--xii",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.4",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Anonymous:2011:OC,
author = "Anonymous",
title = "Organizing Committee",
crossref = "IEEE:2011:PIA",
pages = "xiii--xiii",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.5",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Anonymous:2011:PC,
author = "Anonymous",
title = "Program Committee",
crossref = "IEEE:2011:PIA",
pages = "xiv--xiv",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.6",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Anonymous:2011:R,
author = "Anonymous",
title = "Reviewers",
crossref = "IEEE:2011:PIA",
pages = "xv--xvi",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.7",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Anonymous:2011:TC,
author = "Anonymous",
title = "Table of Contents",
crossref = "IEEE:2011:PIA",
pages = "v--xi",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.9",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Anonymous:2011:TP,
author = "Anonymous",
title = "Title Page i",
crossref = "IEEE:2011:PIA",
pages = "i--i",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.1",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Anonymous:2011:TPI,
author = "Anonymous",
title = "Title Page iii",
crossref = "IEEE:2011:PIA",
pages = "iii--iii",
year = "2011",
DOI = "https://doi.org/10.1109/FOCS.2011.2",
bibdate = "Thu Apr 12 09:34:22 MDT 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
book-URL = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120",
}
@InProceedings{Arora:2012:LTM,
author = "S. Arora and Rong Ge and A. Moitra",
title = "Learning Topic Models -- Going beyond {SVD}",
crossref = "IEEE:2012:PIA",
pages = "1--10",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.49",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375276",
acknowledgement = ack-nhfb,
}
@InProceedings{Valiant:2012:FCS,
author = "G. Valiant",
title = "Finding Correlations in Subquadratic Time, with
Applications to Learning Parities and Juntas",
crossref = "IEEE:2012:PIA",
pages = "11--20",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.27",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375277",
acknowledgement = ack-nhfb,
}
@InProceedings{Balcan:2012:APT,
author = "M.-F. Balcan and E. Blais and A. Blum and Liu Yang",
title = "Active Property Testing",
crossref = "IEEE:2012:PIA",
pages = "21--30",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.64",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375278",
acknowledgement = ack-nhfb,
}
@InProceedings{Goldwasser:2012:HCP,
author = "S. Goldwasser and G. N. Rothblum",
title = "How to Compute in the Presence of Leakage",
crossref = "IEEE:2012:PIA",
pages = "31--40",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.34",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375279",
acknowledgement = ack-nhfb,
}
@InProceedings{Goyal:2012:PRC,
author = "V. Goyal",
title = "Positive Results for Concurrently Secure Computation
in the Plain Model",
crossref = "IEEE:2012:PIA",
pages = "41--50",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.13",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375280",
acknowledgement = ack-nhfb,
}
@InProceedings{Goyal:2012:CNM,
author = "V. Goyal and Chen-Kuei Lee and R. Ostrovsky and I.
Visconti",
title = "Constructing Non-malleable Commitments: A Black-Box
Approach",
crossref = "IEEE:2012:PIA",
pages = "51--60",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.47",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375281",
acknowledgement = ack-nhfb,
}
@InProceedings{Lovett:2012:CDM,
author = "S. Lovett and R. Meka",
title = "Constructive Discrepancy Minimization by Walking on
the Edges",
crossref = "IEEE:2012:PIA",
pages = "61--67",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.23",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375282",
acknowledgement = ack-nhfb,
}
@InProceedings{Kawarabayashi:2012:CCC,
author = "K. Kawarabayashi and M. Thorup",
title = "Combinatorial Coloring of $3$-Colorable Graphs",
crossref = "IEEE:2012:PIA",
pages = "68--75",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.16",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375283",
acknowledgement = ack-nhfb,
}
@InProceedings{Vishnoi:2012:PAT,
author = "N. K. Vishnoi",
title = "A Permanent Approach to the {Traveling Salesman
Problem}",
crossref = "IEEE:2012:PIA",
pages = "76--80",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.81",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375284",
acknowledgement = ack-nhfb,
}
@InProceedings{Busch:2012:SJS,
author = "C. Busch and C. Dutta and J. Radhakrishnan and R.
Rajaraman and S. Srinivasagopalan",
title = "Split and Join: Strong Partitions and Universal
{Steiner} Trees for Graphs",
crossref = "IEEE:2012:PIA",
pages = "81--90",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.45",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375285",
acknowledgement = ack-nhfb,
}
@InProceedings{Kane:2012:STP,
author = "D. M. Kane",
title = "A Structure Theorem for Poorly Anticoncentrated
{Gaussian} Chaoses and Applications to the Study of
Polynomial Threshold Functions",
crossref = "IEEE:2012:PIA",
pages = "91--100",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.52",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375286",
acknowledgement = ack-nhfb,
}
@InProceedings{Beck:2012:LDB,
author = "C. Beck and R. Impagliazzo and S. Lovett",
title = "Large Deviation Bounds for Decision Trees and Sampling
Lower Bounds for {AC0}-Circuits",
crossref = "IEEE:2012:PIA",
pages = "101--110",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.82",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375287",
acknowledgement = ack-nhfb,
}
@InProceedings{Impagliazzo:2012:PS,
author = "R. Impagliazzo and R. Meka and D. Zuckerman",
title = "Pseudorandomness from Shrinkage",
crossref = "IEEE:2012:PIA",
pages = "111--119",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.78",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib;
http://www.math.utah.edu/pub/tex/bib/prng.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375288",
acknowledgement = ack-nhfb,
}
@InProceedings{Gopalan:2012:BPG,
author = "P. Gopalan and R. Meka and O. Reingold and L. Trevisan
and S. Vadhan",
title = "Better Pseudorandom Generators from Milder
Pseudorandom Restrictions",
crossref = "IEEE:2012:PIA",
pages = "120--129",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.77",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib;
http://www.math.utah.edu/pub/tex/bib/prng.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375289",
acknowledgement = ack-nhfb,
}
@InProceedings{Cai:2012:OMD,
author = "Yang Cai and C. Daskalakis and S. M. Weinberg",
title = "Optimal Multi-dimensional Mechanism Design: Reducing
Revenue to Welfare Maximization",
crossref = "IEEE:2012:PIA",
pages = "130--139",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.88",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375290",
acknowledgement = ack-nhfb,
}
@InProceedings{Huang:2012:EMS,
author = "Zhiyi Huang and S. Kannan",
title = "The Exponential Mechanism for Social Welfare: Private,
Truthful, and Nearly Optimal",
crossref = "IEEE:2012:PIA",
pages = "140--149",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.36",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375291",
acknowledgement = ack-nhfb,
}
@InProceedings{Vegh:2012:CGF,
author = "L. A. Vegh",
title = "Concave Generalized Flows with Applications to Market
Equilibria",
crossref = "IEEE:2012:PIA",
pages = "150--159",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.33",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375292",
acknowledgement = ack-nhfb,
}
@InProceedings{Brakerski:2012:EIC,
author = "Z. Brakerski and Y. T. Kalai",
title = "Efficient Interactive Coding against Adversarial
Noise",
crossref = "IEEE:2012:PIA",
pages = "160--166",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.22",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375293",
acknowledgement = ack-nhfb,
}
@InProceedings{Jain:2012:DPT,
author = "R. Jain and A. Pereszlenyi and Penghui Yao",
title = "A Direct Product Theorem for the Two-Party
Bounded-Round Public-Coin Communication Complexity",
crossref = "IEEE:2012:PIA",
pages = "167--176",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.42",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375294",
acknowledgement = ack-nhfb,
}
@InProceedings{Ben-Sasson:2012:ACA,
author = "E. Ben-Sasson and S. Lovett and N. Ron-Zewi",
title = "An Additive Combinatorics Approach Relating Rank to
Communication Complexity",
crossref = "IEEE:2012:PIA",
pages = "177--186",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.39",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375295",
acknowledgement = ack-nhfb,
}
@InProceedings{Gharan:2012:AEP,
author = "S. O. Gharan and L. Trevisan",
title = "Approximating the Expansion Profile and Almost Optimal
Local Graph Clustering",
crossref = "IEEE:2012:PIA",
pages = "187--196",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.85",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375296",
acknowledgement = ack-nhfb,
}
@InProceedings{Guruswami:2012:FSH,
author = "V. Guruswami and A. K. Sinop",
title = "Faster {SDP} Hierarchy Solvers for Local Rounding
Algorithms",
crossref = "IEEE:2012:PIA",
pages = "197--206",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.58",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375297",
acknowledgement = ack-nhfb,
}
@InProceedings{Belovs:2012:LGB,
author = "A. Belovs",
title = "Learning-Graph-Based Quantum Algorithm for
$k$-Distinctness",
crossref = "IEEE:2012:PIA",
pages = "207--216",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.18",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375298",
acknowledgement = ack-nhfb,
}
@InProceedings{Meka:2012:PCS,
author = "R. Meka",
title = "A {PTAS} for Computing the Supremum of {Gaussian}
Processes",
crossref = "IEEE:2012:PIA",
pages = "217--222",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.24",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375299",
acknowledgement = ack-nhfb,
}
@InProceedings{Bitansky:2012:ION,
author = "N. Bitansky and O. Paneth",
title = "From the Impossibility of Obfuscation to a New
Non-Black-Box Simulation Technique",
crossref = "IEEE:2012:PIA",
pages = "223--232",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.40",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375300",
acknowledgement = ack-nhfb,
}
@InProceedings{Chuzhoy:2012:PAA,
author = "J. Chuzhoy and Shi Li",
title = "A Polylogarithmic Approximation Algorithm for
Edge-Disjoint Paths with Congestion $2$",
crossref = "IEEE:2012:PIA",
pages = "233--242",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.54",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375301",
acknowledgement = ack-nhfb,
}
@InProceedings{Ito:2012:MPI,
author = "T. Ito and T. Vidick",
title = "A Multi-prover Interactive Proof for {NEXP} Sound
against Entangled Provers",
crossref = "IEEE:2012:PIA",
pages = "243--252",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.11",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375302",
acknowledgement = ack-nhfb,
}
@InProceedings{Newman:2012:BTP,
author = "A. Newman and O. Neiman and A. Nikolov",
title = "{Beck}'s {Three Permutations Conjecture}: A
Counterexample and Some Consequences",
crossref = "IEEE:2012:PIA",
pages = "253--262",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.84",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375303",
acknowledgement = ack-nhfb,
}
@InProceedings{Fukunaga:2012:IRA,
author = "T. Fukunaga and R. Ravi",
title = "Iterative Rounding Approximation Algorithms for
Degree-Bounded Node-Connectivity Network Design",
crossref = "IEEE:2012:PIA",
pages = "263--272",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.30",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375304",
acknowledgement = ack-nhfb,
}
@InProceedings{Cygan:2012:LRC,
author = "M. Cygan and M. Hajiaghayi and S. Khuller",
title = "{LP} Rounding for $k$-Centers with Non-uniform Hard
Capacities",
crossref = "IEEE:2012:PIA",
pages = "273--282",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.63",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375305",
acknowledgement = ack-nhfb,
}
@InProceedings{Kopelowitz:2012:LIG,
author = "T. Kopelowitz",
title = "On-Line Indexing for General Alphabets via Predecessor
Queries on Subsets of an Ordered List",
crossref = "IEEE:2012:PIA",
pages = "283--292",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.79",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375306",
acknowledgement = ack-nhfb,
}
@InProceedings{Larsen:2012:HCP,
author = "K. G. Larsen",
title = "Higher Cell Probe Lower Bounds for Evaluating
Polynomials",
crossref = "IEEE:2012:PIA",
pages = "293--301",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.21",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375307",
acknowledgement = ack-nhfb,
}
@InProceedings{Doty:2012:TAM,
author = "D. Doty and J. H. Lutz and M. J. Patitz and R. T.
Schweller and S. M. Summers and D. Woods",
title = "The Tile Assembly Model is Intrinsically Universal",
crossref = "IEEE:2012:PIA",
pages = "302--310",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.76",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375308",
acknowledgement = ack-nhfb,
}
@InProceedings{Chazelle:2012:DIS,
author = "B. Chazelle",
title = "The Dynamics of Influence Systems",
crossref = "IEEE:2012:PIA",
pages = "311--320",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.70",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375309",
acknowledgement = ack-nhfb,
}
@InProceedings{Barenboim:2012:LDS,
author = "L. Barenboim and M. Elkin and S. Pettie and J.
Schneider",
title = "The Locality of Distributed Symmetry Breaking",
crossref = "IEEE:2012:PIA",
pages = "321--330",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.60",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375310",
acknowledgement = ack-nhfb,
}
@InProceedings{Alistarh:2012:HAT,
author = "D. Alistarh and M. A. Bender and S. Gilbert and R.
Guerraoui",
title = "How to Allocate Tasks Asynchronously",
crossref = "IEEE:2012:PIA",
pages = "331--340",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.41",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375311",
acknowledgement = ack-nhfb,
}
@InProceedings{Sauerwald:2012:TBR,
author = "T. Sauerwald and He Sun",
title = "Tight Bounds for Randomized Load Balancing on
Arbitrary Network Topologies",
crossref = "IEEE:2012:PIA",
pages = "341--350",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.86",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375312",
acknowledgement = ack-nhfb,
}
@InProceedings{Berkholz:2012:CFN,
author = "C. Berkholz",
title = "On the Complexity of Finding Narrow Proofs",
crossref = "IEEE:2012:PIA",
pages = "351--360",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.48",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375313",
acknowledgement = ack-nhfb,
}
@InProceedings{Sly:2012:CHC,
author = "A. Sly and N. Sun",
title = "The Computational Hardness of Counting in Two-Spin
Models on $d$-Regular Graphs",
crossref = "IEEE:2012:PIA",
pages = "361--369",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.56",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375314",
acknowledgement = ack-nhfb,
}
@InProceedings{Barak:2012:MLC,
author = "B. Barak and P. Gopalan and J. Hastad and R. Meka and
P. Raghavendra and D. Steurer",
title = "Making the Long Code Shorter",
crossref = "IEEE:2012:PIA",
pages = "370--379",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.83",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375315",
acknowledgement = ack-nhfb,
}
@InProceedings{Khot:2012:HFI,
author = "S. Khot and R. Saket",
title = "Hardness of Finding Independent Sets in Almost
$q$-Colorable Graphs",
crossref = "IEEE:2012:PIA",
pages = "380--389",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.75",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375316",
acknowledgement = ack-nhfb,
}
@InProceedings{Wigderson:2012:PRP,
author = "A. Wigderson and A. Yehudayoff",
title = "Population Recovery and Partial Identification",
crossref = "IEEE:2012:PIA",
pages = "390--399",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.14",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375317",
acknowledgement = ack-nhfb,
}
@InProceedings{Dwork:2012:PAP,
author = "C. Dwork and M. Naor and S. Vadhan",
title = "The Privacy of the Analyst and the Power of the
State",
crossref = "IEEE:2012:PIA",
pages = "400--409",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.87",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375318",
acknowledgement = ack-nhfb,
}
@InProceedings{Blocki:2012:JLT,
author = "J. Blocki and A. Blum and A. Datta and O. Sheffet",
title = "The {Johnson--Lindenstrauss Transform} Itself
Preserves Differential Privacy",
crossref = "IEEE:2012:PIA",
pages = "410--419",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.67",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375319",
acknowledgement = ack-nhfb,
}
@InProceedings{Agarwal:2012:RSS,
author = "P. K. Agarwal and J. Matouek and M. Sharir",
title = "On Range Searching with Semialgebraic Sets {II}",
crossref = "IEEE:2012:PIA",
pages = "420--429",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.32",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375320",
acknowledgement = ack-nhfb,
}
@InProceedings{Har-Peled:2012:RHR,
author = "S. Har-Peled and N. Kumar",
title = "Down the Rabbit Hole: Robust Proximity Search and
Density Estimation in Sublinear Space",
crossref = "IEEE:2012:PIA",
pages = "430--439",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.31",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375321",
acknowledgement = ack-nhfb,
}
@InProceedings{Lazarus:2012:HTS,
author = "F. Lazarus and J. Rivaud",
title = "On the Homotopy Test on Surfaces",
crossref = "IEEE:2012:PIA",
pages = "440--449",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.12",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375322",
acknowledgement = ack-nhfb,
}
@InProceedings{Kratsch:2012:RSI,
author = "S. Kratsch and M. Wahlstrom",
title = "Representative Sets and Irrelevant Vertices: New Tools
for Kernelization",
crossref = "IEEE:2012:PIA",
pages = "450--459",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.46",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375323",
acknowledgement = ack-nhfb,
}
@InProceedings{Chitnis:2012:DFA,
author = "R. Chitnis and M. Cygan and M. Hajiaghayi and M.
Pilipczuk and M. Pilipczuk",
title = "Designing {FPT} Algorithms for Cut Problems Using
Randomized Contractions",
crossref = "IEEE:2012:PIA",
pages = "460--469",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.29",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375324",
acknowledgement = ack-nhfb,
}
@InProceedings{Fomin:2012:PDA,
author = "F. V. Fomin and D. Lokshtanov and N. Misra and S.
Saurabh",
title = "Planar {$F$}-Deletion: Approximation, Kernelization
and Optimal {FPT} Algorithms",
crossref = "IEEE:2012:PIA",
pages = "470--479",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.62",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375325",
acknowledgement = ack-nhfb,
}
@InProceedings{Braun:2012:ALL,
author = "G. Braun and S. Fiorini and S. Pokutta and D.
Steurer",
title = "Approximation Limits of Linear Programs (Beyond
Hierarchies)",
crossref = "IEEE:2012:PIA",
pages = "480--489",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.10",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375326",
acknowledgement = ack-nhfb,
}
@InProceedings{Kalai:2012:FRS,
author = "Y. T. Kalai and A. Lewko and A. Rao",
title = "Formulas Resilient to Short-Circuit Errors",
crossref = "IEEE:2012:PIA",
pages = "490--499",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.69",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375327",
acknowledgement = ack-nhfb,
}
@InProceedings{Kerenidis:2012:LBI,
author = "I. Kerenidis and S. Laplante and V. Lerays and J.
Roland and D. Xiao",
title = "Lower Bounds on Information Complexity via
Zero-Communication Protocols and Applications",
crossref = "IEEE:2012:PIA",
pages = "500--509",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.68",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375328",
acknowledgement = ack-nhfb,
}
@InProceedings{Levin:2012:RS,
author = "L. A. Levin",
title = "Rarity for Semimeasures",
crossref = "IEEE:2012:PIA",
pages = "510--513",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.50",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375329",
acknowledgement = ack-nhfb,
}
@InProceedings{LeGall:2012:FAR,
author = "F. {Le Gall}",
title = "Faster Algorithms for Rectangular Matrix
Multiplication",
crossref = "IEEE:2012:PIA",
pages = "514--523",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.80",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375330",
acknowledgement = ack-nhfb,
}
@InProceedings{Benoit:2012:QOM,
author = "A. Benoit and A. Bostan and J. van der Hoeven",
title = "Quasi-optimal Multiplication of Linear Differential
Operators",
crossref = "IEEE:2012:PIA",
pages = "524--530",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.57",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375331",
acknowledgement = ack-nhfb,
}
@InProceedings{Cygan:2012:AAB,
author = "M. Cygan and H. N. Gabow and P. Sankowski",
title = "Algorithmic Applications of {Baur--Strassen's
Theorem}: Shortest Cycles, Diameter and Matchings",
crossref = "IEEE:2012:PIA",
pages = "531--540",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.72",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375332",
acknowledgement = ack-nhfb,
}
@InProceedings{Sohler:2012:AOC,
author = "C. Sohler",
title = "Almost Optimal Canonical Property Testers for
Satisfiability",
crossref = "IEEE:2012:PIA",
pages = "541--550",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.59",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375333",
acknowledgement = ack-nhfb,
}
@InProceedings{Blais:2012:PSF,
author = "E. Blais and A. Weinstein and Y. Yoshida",
title = "Partially Symmetric Functions Are Efficiently
Isomorphism-Testable",
crossref = "IEEE:2012:PIA",
pages = "551--560",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.53",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375334",
acknowledgement = ack-nhfb,
}
@InProceedings{Ben-Sasson:2012:SAI,
author = "E. Ben-Sasson and N. Ron-Zewi and M. Sudan",
title = "Sparse Affine-Invariant Linear Codes Are Locally
Testable",
crossref = "IEEE:2012:PIA",
pages = "561--570",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.38",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375335",
acknowledgement = ack-nhfb,
}
@InProceedings{Chandrasekaran:2012:CPM,
author = "K. Chandrasekaran and L. A. Vegh and S. Vempala",
title = "The Cutting Plane Method Is Polynomial for Perfect
Matchings",
crossref = "IEEE:2012:PIA",
pages = "571--580",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.35",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375336",
acknowledgement = ack-nhfb,
}
@InProceedings{Ramshaw:2012:WSA,
author = "L. Ramshaw and R. E. Tarjan",
title = "A Weight-Scaling Algorithm for Min-Cost Imperfect
Matchings in Bipartite Graphs",
crossref = "IEEE:2012:PIA",
pages = "581--590",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.9",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375337",
acknowledgement = ack-nhfb,
}
@InProceedings{Izumi:2012:NDC,
author = "T. Izumi and T. Wadayama",
title = "A New Direction for Counting Perfect Matchings",
crossref = "IEEE:2012:PIA",
pages = "591--598",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.28",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375338",
acknowledgement = ack-nhfb,
}
@InProceedings{Lacki:2012:SSA,
author = "J. Lacki and Y. Nussbaum and P. Sankowski and C.
Wulff-Nilsen",
title = "Single Source--All Sinks Max Flows in Planar
Digraphs",
crossref = "IEEE:2012:PIA",
pages = "599--608",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.66",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375339",
acknowledgement = ack-nhfb,
}
@InProceedings{Drucker:2012:NLC,
author = "A. Drucker",
title = "New Limits to Classical and Quantum Instance
Compression",
crossref = "IEEE:2012:PIA",
pages = "609--618",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.71",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375340",
acknowledgement = ack-nhfb,
}
@InProceedings{Chattopadhyay:2012:LBI,
author = "A. Chattopadhyay and R. Santhanam",
title = "Lower Bounds on Interactive Compressibility by
Constant-Depth Circuits",
crossref = "IEEE:2012:PIA",
pages = "619--628",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.74",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375341",
acknowledgement = ack-nhfb,
}
@InProceedings{Mulmuley:2012:GCT,
author = "K. D. Mulmuley",
title = "Geometric Complexity Theory V: Equivalence between
Blackbox Derandomization of Polynomial Identity Testing
and Derandomization of {Noether}'s {Normalization
Lemma}",
crossref = "IEEE:2012:PIA",
pages = "629--638",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.15",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375342",
acknowledgement = ack-nhfb,
}
@InProceedings{Christandl:2012:CML,
author = "M. Christandl and B. Doran and M. Walter",
title = "Computing Multiplicities of {Lie} Group
Representations",
crossref = "IEEE:2012:PIA",
pages = "639--648",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.43",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375343",
acknowledgement = ack-nhfb,
}
@InProceedings{Buchbinder:2012:TLT,
author = "N. Buchbinder and M. Feldman and J. Naor and R.
Schwartz",
title = "A Tight Linear Time ($ 1 / 2 $ )-Approximation for
Unconstrained Submodular Maximization",
crossref = "IEEE:2012:PIA",
pages = "649--658",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.73",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375344",
acknowledgement = ack-nhfb,
}
@InProceedings{Filmus:2012:TCA,
author = "Y. Filmus and J. Ward",
title = "A Tight Combinatorial Algorithm for Submodular
Maximization Subject to a Matroid Constraint",
crossref = "IEEE:2012:PIA",
pages = "659--668",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.55",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375345",
acknowledgement = ack-nhfb,
}
@InProceedings{Thapper:2012:PLP,
author = "J. Thapper and S. Zivny",
title = "The Power of Linear Programming for Valued {CSPs}",
crossref = "IEEE:2012:PIA",
pages = "669--678",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.25",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375346",
acknowledgement = ack-nhfb,
}
@InProceedings{Zhandry:2012:HCQ,
author = "M. Zhandry",
title = "How to Construct Quantum Random Functions",
crossref = "IEEE:2012:PIA",
pages = "679--687",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.37",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375347",
acknowledgement = ack-nhfb,
}
@InProceedings{Li:2012:NME,
author = "Xin Li",
title = "Non-malleable Extractors, Two-Source Extractors and
Privacy Amplification",
crossref = "IEEE:2012:PIA",
pages = "688--697",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.26",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375348",
acknowledgement = ack-nhfb,
}
@InProceedings{Holenstein:2012:CPG,
author = "T. Holenstein and M. Sinha",
title = "Constructing a Pseudorandom Generator Requires an
Almost Linear Number of Calls",
crossref = "IEEE:2012:PIA",
pages = "698--707",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.51",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib;
http://www.math.utah.edu/pub/tex/bib/prng.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375349",
acknowledgement = ack-nhfb,
}
@InProceedings{Poloczek:2012:RGA,
author = "M. Poloczek and M. Szegedy",
title = "Randomized Greedy Algorithms for the Maximum Matching
Problem with New Analysis",
crossref = "IEEE:2012:PIA",
pages = "708--717",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.20",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375350",
acknowledgement = ack-nhfb,
}
@InProceedings{Goel:2012:MOE,
author = "G. Goel and P. Tripathi",
title = "Matching with Our Eyes Closed",
crossref = "IEEE:2012:PIA",
pages = "718--727",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.19",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375351",
acknowledgement = ack-nhfb,
}
@InProceedings{Mehta:2012:OMS,
author = "A. Mehta and D. Panigrahi",
title = "Online Matching with Stochastic Rewards",
crossref = "IEEE:2012:PIA",
pages = "728--737",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.65",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375352",
acknowledgement = ack-nhfb,
}
@InProceedings{Patrascu:2012:NID,
author = "M. Patrascu and L. Roditty and M. Thorup",
title = "A New Infinity of Distance Oracles for Sparse Graphs",
crossref = "IEEE:2012:PIA",
pages = "738--747",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.44",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375353",
acknowledgement = ack-nhfb,
}
@InProceedings{Grandoni:2012:IDS,
author = "F. Grandoni and V. V. Williams",
title = "Improved Distance Sensitivity Oracles via Fast
Single-Source Replacement Paths",
crossref = "IEEE:2012:PIA",
pages = "748--757",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.17",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375354",
acknowledgement = ack-nhfb,
}
@InProceedings{Chlamtac:2012:ESS,
author = "E. Chlamta{\'c} and M. Dinitz and R. Krauthgamer",
title = "Everywhere-Sparse Spanners via Dense Subgraphs",
crossref = "IEEE:2012:PIA",
pages = "758--767",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.61",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375355",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2012:AI,
author = "Anonymous",
title = "Author index",
crossref = "IEEE:2012:PIA",
pages = "768--770",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.90",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375356",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2012:PI,
author = "Anonymous",
title = "[Publisher's information]",
crossref = "IEEE:2012:PIA",
pages = "772--772",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.91",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375357",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2012:OC,
author = "Anonymous",
title = "Organizing Committee",
crossref = "IEEE:2012:PIA",
pages = "xiv--xiv",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.5",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375362",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2012:A,
author = "Anonymous",
title = "Awards",
crossref = "IEEE:2012:PIA",
pages = "xix--xix",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.89",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375365",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2012:R,
author = "Anonymous",
title = "Reviewers",
crossref = "IEEE:2012:PIA",
pages = "xvi--xviii",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.7",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375364",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2012:TPa,
author = "Anonymous",
title = "Title page",
crossref = "IEEE:2012:PIA",
pages = "i--i",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.1",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375358",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2012:PC,
author = "Anonymous",
title = "Program Committee",
crossref = "IEEE:2012:PIA",
pages = "xv--xv",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.6",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375363",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2012:BC,
author = "Anonymous",
title = "Back cover",
crossref = "IEEE:2012:PIA",
pages = "C4--C4",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.92",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375366",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2012:TPb,
author = "Anonymous",
title = "Title page",
crossref = "IEEE:2012:PIA",
pages = "iii--iii",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.2",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375359",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2012:TC,
author = "Anonymous",
title = "Table of contents",
crossref = "IEEE:2012:PIA",
pages = "v--xi",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.8",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375367",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2012:CN,
author = "Anonymous",
title = "Copyright notice",
crossref = "IEEE:2012:PIA",
pages = "iv--iv",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.3",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375360",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2012:F,
author = "Anonymous",
title = "Foreword",
crossref = "IEEE:2012:PIA",
pages = "xii--xiii",
year = "2012",
DOI = "https://doi.org/10.1109/FOCS.2012.4",
bibdate = "Tue Jul 30 12:28:46 MDT 2013",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
URL = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6375361",
acknowledgement = ack-nhfb,
}
@InProceedings{Adamaszek:2013:ASM,
author = "A. Adamaszek and A. Wiese",
title = "Approximation Schemes for Maximum Weight Independent
Set of Rectangles",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Alaei:2013:SEA,
author = "S. Alaei and Hu Fu and N. Haghpanah and J. Hartline",
title = "The Simple Economics of Approximately Optimal
Auctions",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2013:A,
author = "Anonymous",
title = "Awards",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2013:AI,
author = "Anonymous",
title = "Author Index",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:24 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2013:CA,
author = "Anonymous",
title = "Cover Art",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2013:CP,
author = "Anonymous",
title = "Copyright Page",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2013:F,
author = "Anonymous",
title = "Foreword",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2013:OCS,
author = "Anonymous",
title = "Organizing Committee and Sponsors",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2013:PAa,
author = "Anonymous",
title = "Proceedings Available",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2013:PAb,
author = "Anonymous",
title = "Proceedings Available",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:24 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2013:PC,
author = "Anonymous",
title = "Program Committee",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2013:QLa,
author = "Anonymous",
title = "Quick Links",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2013:QLb,
author = "Anonymous",
title = "Quick Links",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:24 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2013:R,
author = "Anonymous",
title = "Reviewers",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2013:TC,
author = "Anonymous",
title = "Table of contents",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2013:TP,
author = "Anonymous",
title = "Title Page i",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2013:TPI,
author = "Anonymous",
title = "Title Page iii",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Arora:2013:TBA,
author = "S. Arora and Rong Ge and A. K. Sinop",
title = "Towards a Better Approximation for Sparsest Cut?",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Avigdor-Elgrabli:2013:ICA,
author = "N. Avigdor-Elgrabli and Y. Rabani",
title = "An Improved Competitive Algorithm for Reordering
Buffer Management",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Babai:2013:FCF,
author = "L. Babai and Xi Chen and Xiaorui Sun and Shang-Hua
Teng and J. Wilmes",
title = "Faster Canonical Forms for Strongly Regular Graphs",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Badanidiyuru:2013:BK,
author = "A. Badanidiyuru and R. Kleinberg and A. Slivkins",
title = "Bandits with Knapsacks",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Bartal:2013:LTA,
author = "Y. Bartal and L.-A. Gottlieb",
title = "A Linear Time Approximation Scheme for {Euclidean}
{TSP}",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:24 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Bassily:2013:CWP,
author = "R. Bassily and A. Groce and J. Katz and A. Smith",
title = "Coupled-Worlds Privacy: Exploiting Adversarial
Uncertainty in Statistical Data Privacy",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Beame:2013:EDF,
author = "P. Beame and R. Clifford and W. Machmouchi",
title = "Element Distinctness, Frequency Moments, and Sliding
Windows",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Ben-Sasson:2013:CRP,
author = "E. Ben-Sasson and Y. Kaplan and S. Kopparty and O.
Meir and H. Stichtenoth",
title = "Constant Rate {PCPs} for Circuit-{SAT} with Sublinear
Query Complexity",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Bilo:2013:PSU,
author = "V. Bilo and M. Flammini and L. Moscardelli",
title = "The Price of Stability for Undirected Broadcast
Network Design with Fair Cost Allocation Is Constant",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:24 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Bjorklund:2013:PDH,
author = "A. Bjorklund and T. Husfeldt",
title = "The Parity of Directed {Hamiltonian} Cycles",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:24 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Bodlaender:2013:CAA,
author = "H. L. Bodlaender and P. G. Drange and M. S. Dregi and
F. V. Fomin and D. Lokshtanov and M. Pilipczuk",
title = "An {$ O(c^k n) $} $5$-Approximation Algorithm for
Treewidth",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Braun:2013:CIU,
author = "G. Braun and S. Pokutta",
title = "Common Information and Unique Disjointness",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:24 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Braverman:2013:DPC,
author = "M. Braverman and A. Rao and O. Weinstein and A.
Yehudayoff",
title = "Direct Products in Communication Complexity",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:24 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Braverman:2013:TBS,
author = "M. Braverman and F. Ellen and R. Oshman and T. Pitassi
and V. Vaikuntanathan",
title = "A Tight Bound for Set Disjointness in the
Message-Passing Model",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:24 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Cai:2013:UIM,
author = "Yang Cai and C. Daskalakis and S. M. Weinberg",
title = "Understanding Incentives: Mechanism Design Becomes
Algorithm Design",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Canetti:2013:UEF,
author = "R. Canetti and Huijia Lin and R. Pass",
title = "From Unprovability to Environmentally Friendly
Protocols",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Chalermsook:2013:ISI,
author = "P. Chalermsook and B. Laekhanukit and D. Nanongkai",
title = "Independent Set, Induced Matching, and Pricing:
Connections and Tight (Subexponential Time)
Approximation Hardnesses",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Chan:2013:ACS,
author = "Siu On Chan and J. R. Lee and P. Raghavendra and D.
Steurer",
title = "Approximate Constraint Satisfaction Requires Large
{LP} Relaxations",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Chan:2013:KMP,
author = "T. M. Chan",
title = "{Klee}'s Measure Problem Made Easy",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Chekuri:2013:AAE,
author = "C. Chekuri and A. Sidiropoulos",
title = "Approximation Algorithms for {Euler} Genus and Related
Problems",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Chen:2013:CIV,
author = "D. Z. Chen and Ziyun Huang and Yangwei Liu and Jinhui
Xu",
title = "On Clustering Induced {Voronoi} Diagrams",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Cheriyan:2013:AMC,
author = "J. Cheriyan and L. A. Vegh",
title = "Approximating Minimum-Cost $k$-Node Connected
Subgraphs via Independence-Free Graphs",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Chiplunkar:2013:RMA,
author = "A. Chiplunkar and S. Vishwanathan",
title = "On Randomized Memoryless Algorithms for the Weighted
{$K$}-Server Problem",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Chung:2013:CRC,
author = "Kai-Min Chung and Huijia Lin and R. Pass",
title = "Constant-Round Concurrent Zero Knowledge from
{$P$}-Certificates",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Chung:2013:KPI,
author = "Kai-Min Chung and R. Pass and S. Telang",
title = "Knowledge-Preserving Interactive Coding",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Chung:2013:SRO,
author = "Kai-Min Chung and R. Ostrovsky and R. Pass and I.
Visconti",
title = "Simultaneous Resettability from One-Way Functions",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Coja-Oghlan:2013:CKC,
author = "A. Coja-Oghlan and D. Vilenchik",
title = "Chasing the {$K$}-Colorability Threshold",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Cygan:2013:IAD,
author = "M. Cygan",
title = "Improved Approximation for $3$-Dimensional Matching
via Bounded Pathwidth Local Search",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Cygan:2013:PDK,
author = "M. Cygan and D. Marx and M. Pilipczuk and M.
Pilipczuk",
title = "The Planar Directed {K}-Vertex-Disjoint Paths Problem
Is Fixed-Parameter Tractable",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Daskalakis:2013:LSI,
author = "C. Daskalakis and I. Diakonikolas and R. ODonnell and
R. A. Servedio and Li-Yang Tan",
title = "Learning Sums of Independent Integer Random
Variables",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Dinur:2013:PLD,
author = "I. Dinur and V. Guruswami",
title = "{PCPs} via Low-Degree Long Code and Hardness for
Constrained Hypergraph Coloring",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Drucker:2013:NDP,
author = "A. Drucker",
title = "Nondeterministic Direct Product Reductions and the
Success Probability of {SAT} Solvers",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:24 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Duchi:2013:LPS,
author = "J. C. Duchi and M. I. Jordan and M. J. Wainwright",
title = "Local Privacy and Statistical Minimax Rates",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Dujmovic:2013:LSQ,
author = "V. Dujmovic and P. Morin and D. R. Wood",
title = "Layered Separators for Queue Layouts, {$3$D} Graph
Drawing and Nonrepetitive Coloring",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Feldman:2013:OBA,
author = "V. Feldman and J. Vondrak",
title = "Optimal Bounds on Approximation of Submodular and
{XOS} Functions by Juntas",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Filmus:2013:ACL,
author = "Y. Filmus and T. Pitassi and R. Robere and S. A.
Cook",
title = "Average Case Lower Bounds for Monotone Switching
Networks",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Forbes:2013:QTI,
author = "M. A. Forbes and A. Shpilka",
title = "Quasipolynomial-Time Identity Testing of
Non-commutative and {Read}-Once Oblivious Algebraic
Branching Programs",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Gabow:2013:AAB,
author = "H. N. Gabow and P. Sankowski",
title = "Algebraic Algorithms for {$B$}-Matching, Shortest
Undirected Paths, and {$F$}-Factors",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Garay:2013:RPD,
author = "J. Garay and J. Katz and U. Maurer and B. Tackmann and
V. Zikas",
title = "Rational Protocol Design: Cryptography against
Incentive-Driven Adversaries",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:24 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Garber:2013:PNL,
author = "D. Garber and E. Hazan",
title = "Playing Non-linear Games with Linear Oracles",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Garg:2013:CIO,
author = "S. Garg and C. Gentry and S. Halevi and M. Raykova and
A. Sahai and B. Waters",
title = "Candidate Indistinguishability Obfuscation and
Functional Encryption for all Circuits",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Gaspers:2013:SBB,
author = "S. Gaspers and S. Szeider",
title = "Strong Backdoors to Bounded Treewidth {SAT}",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Gosset:2013:QSQ,
author = "D. Gosset and D. Nagaj",
title = "Quantum $3$-{SAT} Is {QMA1}-Complete",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:24 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Gupta:2013:ACC,
author = "A. Gupta and P. Kamath and N. Kayal and R.
Saptharishi",
title = "Arithmetic Circuits: A Chasm at Depth Three",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Gupta:2013:FDA,
author = "M. Gupta and R. Peng",
title = "Fully Dynamic $ (1 + e) $-Approximate Matchings",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Guruswami:2013:ESD,
author = "V. Guruswami and S. Kopparty",
title = "Explicit Subspace Designs",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Guruswami:2013:PCS,
author = "V. Guruswami and P. Xia",
title = "Polar Codes: Speed of Polarization and Polynomial Gap
to Capacity",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Hajiaghayi:2013:ONW,
author = "M. T. Hajiaghayi and V. Liaghat and D. Panigrahi",
title = "Online Node-Weighted {Steiner} Forest and Extensions
via Disk Paintings",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Har-Peled:2013:AMD,
author = "S. Har-Peled and N. Kumar",
title = "Approximating Minimization Diagrams and Generalized
Proximity Search",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:24 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Harris:2013:MTF,
author = "D. G. Harris and A. Srinivasan",
title = "The {Moser--Tardos} Framework with Partial
Resampling",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Hatami:2013:EDT,
author = "H. Hatami and S. Lovett",
title = "Estimating the Distance from Testable Affine-Invariant
Properties",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Henzinger:2013:DAA,
author = "M. Henzinger and S. Krinninger and D. Nanongkai",
title = "Dynamic Approximate All-Pairs Shortest Paths: Breaking
the {$ O(m n) $} Barrier and Derandomization",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Impagliazzo:2013:SAS,
author = "R. Impagliazzo and R. Paturi and S. Schneider",
title = "A Satisfiability Algorithm for Sparse Depth Two
Threshold Circuits",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Kawarabayashi:2013:ANM,
author = "K.-I. Kawarabayashi and Y. Kobayashi",
title = "All-or-Nothing Multicommodity Flow Problem with
Bounded Fractionality in Planar Graphs",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Komargodski:2013:IAC,
author = "I. Komargodski and R. Raz and A. Tal",
title = "Improved Average-Case Lower Bounds for {DeMorgan}
Formula Size",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Konemann:2013:LLA,
author = "J. Konemann and S. Sadeghian and L. Sanita",
title = "An {LMP} {$ O(\log n) $}-Approximation Algorithm for
Node Weighted Prize Collecting {Steiner} Tree",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Lee:2013:EAC,
author = "Yin Tat Lee and A. Sidford",
title = "Efficient Accelerated Coordinate Descent Methods and
Faster Algorithms for Solving Linear Systems",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Li:2013:ECN,
author = "Xin Li",
title = "Extractors for a Constant Number of Independent
Sources with Polylogarithmic Min-Entropy",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Li:2013:IRS,
author = "Mu Li and G. L. Miller and R. Peng",
title = "Iterative Row Sampling",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Louis:2013:CAV,
author = "A. Louis and P. Raghavendra and S. Vempala",
title = "The Complexity of Approximating Vertex Expansion",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Madry:2013:NCP,
author = "A. Madry",
title = "Navigating Central Path with Electrical Flows: From
Flows to Matchings, and Back",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Marcus:2013:IFB,
author = "A. Marcus and D. A. Spielman and N. Srivastava",
title = "Interlacing Families {I}: Bipartite {Ramanujan} Graphs
of All Degrees",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Moitra:2013:PTA,
author = "A. Moitra and M. Saks",
title = "A Polynomial Time Algorithm for Lossy Population
Recovery",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Nelson:2013:OFN,
author = "J. Nelson and H. L. Nguyen",
title = "{OSNAP}: Faster Numerical Linear Algebra Algorithms
via Sparser Subspace Embeddings",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2013:PI,
author = "Anonymous",
title = "{Publisher}'s Information",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:24 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Pagh:2013:HAS,
author = "R. Pagh and G. Segev and U. Wieder",
title = "How to Approximate a Set without Knowing Its Size in
Advance",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Rothvoss:2013:APW,
author = "T. Rothvoss",
title = "Approximating Bin Packing within {$ O(\log {\rm OPT} *
\Log \Log {\rm OPT}) $} Bins",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Rubin:2013:KDT,
author = "N. Rubin",
title = "On Kinetic {Delaunay} Triangulations: A Near Quadratic
Bound for Unit Speed Motions",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Saglam:2013:CCS,
author = "M. Saglam and G. Tardos",
title = "On the Communication Complexity of Sparse Set
Disjointness and Exists-Equal Problems",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:24 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Seeman:2013:ASS,
author = "L. Seeman and Y. Singer",
title = "Adaptive Seeding in Social Networks",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Sherman:2013:NMF,
author = "J. Sherman",
title = "Nearly Maximum Flows in Nearly Linear Time",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Sidiropoulos:2013:NPC,
author = "A. Sidiropoulos",
title = "Non-positive Curvature and the Planar Embedding
Conjecture",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Sinclair:2013:SMA,
author = "A. Sinclair and P. Srivastava and Yitong Yin",
title = "Spatial Mixing and Approximation Algorithms for Graphs
with Bounded Connective Constant",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Thorup:2013:STF,
author = "M. Thorup",
title = "Simple Tabulation, Fast Expanders, Double Tabulation,
and High Independence",
crossref = "IEEE:2013:PIA",
pages = "90--99",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib;
http://www.math.utah.edu/pub/tex/bib/hash.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Tsang:2013:FSS,
author = "Hing Yin Tsang and Chung Hoi Wong and Ning Xie and
Shengyu Zhang",
title = "{Fourier} Sparsity, Spectral Norm, and the Log-Rank
Conjecture",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:24 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Viderman:2013:SLI,
author = "M. Viderman",
title = "Strong {LTCs} with Inverse Poly-Log Rate and Constant
Soundness",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:16 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Vidick:2013:TPE,
author = "T. Vidick",
title = "Three-Player Entangled {XOR} Games Are {NP}-Hard to
Approximate",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:24 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@InProceedings{Wilson:2013:FBS,
author = "D. B. Wilson and U. Zwick",
title = "A Forward-Backward Single-Source Shortest Paths
Algorithm",
crossref = "IEEE:2013:PIA",
pages = "??--??",
year = "2013",
bibdate = "Tue Mar 4 08:32:24 MST 2014",
bibsource = "http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
acknowledgement = ack-nhfb,
}
@Proceedings{IEEE:2010:PIA,
editor = "{IEEE}",
booktitle = "{Proceedings of the 2010 IEEE 51st Annual Symposium on
Foundations of Computer Science: 23--26 October 2010,
Las Vegas, Nevada, USA}",
title = "{Proceedings of the 2010 IEEE 51st Annual Symposium on
Foundations of Computer Science: 23--26 October 2010,
Las Vegas, Nevada, USA}",
publisher = pub-IEEE,
address = pub-IEEE:adr,
pages = "xvi + 826",
year = "2010",
ISBN = "0-7695-4244-1, 1-4244-8525-8",
ISBN-13 = "978-0-7695-4244-7, 978-1-4244-8525-3",
ISSN = "0272-5428",
LCCN = "QA76 .S95 2010",
bibdate = "Tue Nov 06 06:59:58 2012",
bibsource = "fsz3950.oclc.org:210/WorldCat;
http://www.math.utah.edu/pub/tex/bib/focs.bib;
http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
note = "IEEE Computer Society order number P4244.",
URL = "http://opac.ieeecomputersociety.org/opac?year=2010&volume=00&catalog=4244&acronym=focs",
acknowledgement = ack-nhfb,
subject = "electronic data processing; congresses; machine
theory",
}
@Proceedings{IEEE:2011:PIA,
editor = "{IEEE}",
booktitle = "{Proceedings of the 2011 IEEE 52nd Annual Symposium on
Foundations of Computer Science: 22--25 October 2011,
Palm Springs, California, USA}",
title = "{Proceedings of the 2011 IEEE 52nd Annual Symposium on
Foundations of Computer Science: 22--25 October 2011,
Palm Springs, California, USA}",
publisher = pub-IEEE,
address = pub-IEEE:adr,
pages = "????",
year = "2011",
ISBN = "0-7695-4571-8, 1-4577-1843-X",
ISBN-13 = "978-0-7695-4571-4, 978-1-4577-1843-4",
ISSN = "0272-5428",
LCCN = "QA76 .S95 2011",
bibdate = "Tue Nov 06 07:01:39 2012",
bibsource = "fsz3950.oclc.org:210/WorldCat;
http://www.math.utah.edu/pub/tex/bib/focs.bib;
http://www.math.utah.edu/pub/tex/bib/focs2010.bib",
note = "IEEE Computer Society order number P4571.",
URL = "http://opac.ieeecomputersociety.org/opac?year=2011&volume=00&catalog=4571&acronym=focs",
acknowledgement = ack-nhfb,
subject = "electronic data processing; congresses; machine
theory",
}
@Proceedings{IEEE:2012:PIA,
editor = "{IEEE}",
booktitle = "{Proceedings of the 2012 IEEE 53rd Annual Symposium on
Foundations of Computer Science: 20--23 October 2012,
Hyatt Regency, New Brunswick, New Jersey, USA}",
title = "{Proceedings of the 2012 IEEE 53rd Annual Symposium on
Foundations of Computer Science: 20--23 October 2012,
Hyatt Regency, New Brunswick, New Jersey, USA}",
publisher = pub-IEEE,
address = pub-IEEE:adr,
pages = "xix + 772",
year = "2012",
ISBN = "1-4673-4383-8",
ISBN-13 = "978-1-4673-4383-1",
ISSN = "0272-5428",
ISSN-L = "0272-5428",
LCCN = "QA76 .S95 2012",
bibdate = "Tue Nov 06 07:01:39 2012",
bibsource = "fsz3950.oclc.org:210/WorldCat;
http://www.math.utah.edu/pub/tex/bib/focs.bib;
http://www.math.utah.edu/pub/tex/bib/focs2010.bib;
http://www.math.utah.edu/pub/tex/bib/prng.bib",
note = "IEEE Computer Society order number P????.",
URL = "http://dimacs.rutgers.edu/FOCS12/;
http://theory.stanford.edu/~tim/focs12/",
acknowledgement = ack-nhfb,
subject = "electronic data processing; congresses; machine
theory",
}
@Proceedings{IEEE:2013:PIA,
editor = "{IEEE}",
booktitle = "{Proceedings of the 2013 IEEE 54th Annual Symposium on
Foundations of Computer Science: 26--29 October 2013,
Berkeley, CA, USA}",
title = "{Proceedings of the 2012 IEEE 54th Annual Symposium on
Foundations of Computer Science: 26--29 October 2013,
Berkeley, CA, USA}",
publisher = pub-IEEE,
address = pub-IEEE:adr,
pages = "????",
year = "2013",
ISBN = "0-7695-5135-1",
ISBN-13 = "978-0-7695-5135-7",
ISSN = "0272-5428",
ISSN-L = "0272-5428",
LCCN = "QA76 .S95 2012",
bibdate = "Tue Nov 06 07:01:39 2012",
bibsource = "fsz3950.oclc.org:210/WorldCat;
http://www.math.utah.edu/pub/tex/bib/focs.bib;
http://www.math.utah.edu/pub/tex/bib/focs2010.bib;
http://www.math.utah.edu/pub/tex/bib/hash.bib",
note = "IEEE Computer Society order number P????.",
URL = "http://dimacs.rutgers.edu/FOCS13/;
http://theory.stanford.edu/~tim/focs13/",
acknowledgement = ack-nhfb,
subject = "electronic data processing; congresses; machine
theory",
}
