@inproceedings{DBLP:conf/soda/BhattacharyyaFL13,
  author    = {Arnab Bhattacharyya and
               Eldar Fischer and
               Shachar Lovett},
  title     = {Testing Low Complexity Affine-Invariant Properties},
  booktitle = {SODA},
  year      = {2013},
  pages     = {1337-1355},
  ee        = {http://knowledgecenter.siam.org/0236-000105/},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DBLP:conf/stoc/BhowmickDL13,
  author    = {Abhishek Bhowmick and
               Zeev Dvir and
               Shachar Lovett},
  title     = {New bounds for matching vector families},
  booktitle = {STOC},
  year      = {2013},
  pages     = {823-832},
  ee        = {http://doi.acm.org/10.1145/2488608.2488713},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{DBLP:journals/algorithmica/BateniC13,
  author    = {MohammadHossein Bateni and
               Julia Chuzhoy},
  title     = {Approximation Algorithms for the Directed {\it k}-Tour
               and {\it k}-Stroll Problems},
  journal   = {Algorithmica},
  volume    = {65},
  number    = {3},
  year      = {2013},
  pages     = {545-561},
  ee        = {http://dx.doi.org/10.1007/s00453-011-9610-6},
 note = {Earlier version in APPROX 2010}
 }

@article{DBLP:journals/rsa/KhotN13,
  author    = {Subhash Khot and Assaf Naor},
  title     = {Sharp kernel clustering algorithms and their associated Grothendieck inequalities},
  journal   = {Random Struct. Algorithms},
  volume    = {42},
  number    = {3},
  year      = {2013},
  pages     = {269-300},
  ee        = {http://dx.doi.org/10.1002/rsa.20398},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{KhotST12,
  author =	 {Subhash Khot and Muli Safra and Madhur Tulsiani},
  title =	 {Towards an Optimal Query Efficient {PCP}?},
  booktitle =	 {ITCS},
  year =	 2013
}

@inproceedings{DBLP:conf/stoc/BeckNT13,
  author    = {Chris Beck and
               Jakob Nordstr{\"o}m and
               Bangsheng Tang},
  title     = {Some trade-off results for polynomial calculus: extended
               abstract},
  booktitle = {STOC},
  year      = {2013},
  pages     = {813-822},
  ee        = {http://doi.acm.org/10.1145/2488608.2488711},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DH13,
  author = {Zeev Dvir and Guangda Hu},
  title = {Matching-Vector Families and {LDC}s Over Large Modulo},
  booktitle = {RANDOM'13},
  year = {2013},
}




%Michael Saks

@inproceedings{BKS-ran13,
  author    = {Jan Bul{\'a}nek and
               Michal Kouck{\'y} and
               Michael Saks},
  title     = {On randomized labeling with polynomially many labels},
  booktitle = {ICALP},
  year      = {2013},
}

@inproceedings{MS13,
author={Ankur Moitra and Michael Saks},
title={A polynomial time algorithm for lossy population recovery},
booktitle={FOCS},
year={2013}
}

@inproceedings{GSS13,
author = {Justin Gilmer and Srikanth Srinivasan and Michael Saks},
title = {Composition limits and separating examples for some Boolean function complexity measures},
booktitle = {IEEE Conference on Computation Complexity},
year = {2013},
}

@inproceedings{BDLS13,
  author    ={Yonatan Bilu and Amit Daniely and Nati Linial and Michael Saks},
  title     ={On the practically interesting instances of MAXCUT},
booktitle = {Symposium on Theoretical Aspects of Computer Science (STACS)},
  year      ={2013},
  note      ={http://arxiv.org/abs/1205.4893}
}

@inproceedings{SS13,
author = {C. Seshadhri and Michael Saks},
title= {Space efficient streaming algorithms for the distance to monotonicity and assymmetric edit distance},
booktitle= {SODA},
year = {2013}
}

@unpublished{NS13,
author = {Timothy Naumovitz and Michael Saks},
title = {Deterministic streaming algorithms for distance to monotonicity},
year = {2013},
note = {Manuscript, in preparation}
}

@Article{HaeuplerST2013,
  author =	"Bernhard Haeupler and Siddhartha Sen and Robert E. Tarjan",
  title = "Rank-balanced Trees",
  journal =	"ACM Trans. Alg.",
  year = 2013,
  note = "Under revision"
}

@Misc{SenT2013a,
  author =	"Siddhartha Sen and Robert E. Tarjan",
  title =	"Deletion Without Rebalancing in Binary Search Trees",
  year = 	"2013",
  note = "Submitted"
}

@Article{SenT2013b,
  author =	"Bernhard Haeupler and Siddhartha Sen and Robert E. Tarjan",
  title =	"Deletion Without Rebalancing in Multiway Search Trees",
  journal =	"ACM Trans. Database Syst.",
  year = 	"2013",
  note = "Under revision"
}

@Misc{LarkinST2013,
  author =	"Daniel H. Larkin and Siddhartha Sen and Robert E. Tarjan",
  title =	"Experimental Heaps: a Comparative Study of Priority Queues",
  year = 	"2013",
  note = "Submitted"
}

@Misc{GoelKLT2013,
  author =	{Ashish Goel and Sanjeev Khanna and Daniel H. Larkin and Robert E. Tarjan},
  title =	"Disjoint Set Union with Randomized Linking",
  year = 	"2013",
  note = "Submitted"
}

@inproceedings{GeorgiadisLPT2013,
  author    = {Loukas Georgiadis and
               Luigi Laura and
               Nikos Parotsidis and
               Robert Endre Tarjan},
  title     = {Dominator Certification and Independent Spanning Trees:
               An Experimental Study},
  booktitle = {International Symposium on Experimental Algorithms (SEA)},
  year      = {2013},
  pages     = {284-295},
}

@Misc{SchwartzS2013,
  author =	"Jarett Schwartz and Siddhartha Sen",
  title =	"Coalescing Balls and Bins",
  year = 	"2013",
  note = "Submitted"
}

@inproceedings{jetstream-hotos13,
 author = {Rabkin, Ariel and Arye, Matvey and Sen, Siddhartha and Pai, Vivek and Freedman, Michael J.},
 title = {Making every bit count in wide-area analytics},
 booktitle = {USENIX Conference on Hot Topics in Operating Systems (HotOS)},
 year = {2013},
 pages = {6--6},
} 

@misc{jetstream2013,
 author = {Rabkin, Ariel and Arye, Matvey and Sen, Siddhartha and Pai, Vivek and Freedman, Michael J.},
 title = {Analyzing Data Across Continents: Dynamic adaptation for real-time distributed analytics},
 year = {2013},
 note = "Submitted"
} 

@Misc{ChechikLRSTW2013,
  author =	"Shiri Chechik and Daniel H. Larkin and Liam Roditty and Grant Schoenebeck and Robert E. Tarjan and Virginia Vassilevska Williams",
  title =	"Better Approximation Algorithms for the Graph Diameter",
  year = 	"2013",
  note = "Submitted"
}




% Raghu

@misc{MekaW13,
author = {Raghu Meka and Avi Wigderson},
title = {Association Schemes, Non-Commutative Polynomials and Lasserre Lower Bounds for Planted Clique},
note = {Manuscript},
year = {2013}
}

@inproceedings{KaneKM13,
author = {Daniel Kane and Adam Klivans and Raghu Meka},
title = {Learning Halfspaces Under Log-Concave Densities: Polynomial Approximations and Moment Matching},
booktitle = {Conference on Learning Theory},
year      = {2013}
}



%Jing

@UNPUBLISHED{CZ13,
  AUTHOR = {J. Chen and A. Zinger},
  TITLE = {The Robustness of Extortion in Iterated Prisoner's Dilemma},
  NOTE = {Under review at \emph{Journal of Economic Theory}},
  YEAR = {2013},
}

@UNPUBLISHED{BCK13,
  AUTHOR = {M. Braverman and J. Chen and S. Kannan},
  TITLE = {Optimal Provision-After-Wait in Healthcare},
  NOTE = {Working paper},
  YEAR = {2013},
}

@UNPUBLISHED{AIKMNPS13,
  AUTHOR = {A. Antoniodis and S. Im and R. Krishnaswamy and B. Moseley and V. Nagarajan and K. Pruhs and C. Stein},
  TITLE = {Hallucination Helps: Better algorithms for Energy Efficient Routing},
  NOTE = {Submitted to SODA 2014},
  YEAR = {2013},
}

@UNPUBLISHED{KNPS13,
  AUTHOR = {R. Krishnaswamy and V. Nagarajan and K. Pruhs and C. Stein},
  TITLE = {Energy Efficient and Capacitated Network Design with Node Costs},
  NOTE = {Manuscript},
  YEAR = {2013},
}

@UNPUBLISHED{BCKL13,
  AUTHOR = {N. Bansal and M. Charikar and R. Krishnaswamy and S. Li},
  TITLE = {Better Algorithms and Hardness for Broadcast Scheduling using a Discrepancy Approach},
  NOTE = {Submitted to SODA 2014},
  YEAR = {2013},
}



%Moses-group

@INPROCEEDINGS{LS13,
  AUTHOR = {S. Li and O. Svensson},
  TITLE = {Approximating $k$-Median via Pseudo-Approximation},
  BOOKTITLE = {Proceedings of 43th ACM Symposium on the Theory of Computing (STOC 2013)},
  YEAR = {2013},
}

@inproceedings{NN13-osnap,
  author    = {Jelani Nelson and Huy L. Nguyen},
  title     = {{OSNAP}: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings},
  booktitle = {FOCS},
  year      = {2013},
}

@inproceedings{ANPW13,
  author = {Alexandr Andoni and Huy L. Nguyen and Yury Polyanskiy and Yihong Wu},
  title = {Tight Lower Bound for Linear Sketches of Moments},
  booktitle = {ICALP},
  year = {2013},
}

@inproceedings{BBCN13,
  author    = {Arnab Bhattacharyya and Mark Braverman and Bernard Chazelle and Huy L. Nguyen},
  title     = {On the convergence of the {Hegselmann--Krause} system},
  booktitle = {ITCS},
  year      = {2013},
  pages     = {61--66},
}

@inproceedings{AN13,
  author    = {Alexandr Andoni and
               Huy L. Nguyen},
  title     = {Eigenvalues of a matrix in the streaming model},
  booktitle = {SODA},
  year      = {2013},
  pages     = {1729--1737},
}

@inproceedings{NN13-lb,
  author    = {Jelani Nelson and
               Huy L. Nguyen},
  title     = {Sparsity lower bounds for dimensionality reducing maps},
  booktitle = {STOC},
  year      = {2013},
  pages     = {101--110},
}

@inproceedings{chakraborty2013instructor,
  title={Instructor rating markets},
  author={Chakraborty, Mithun and Das, Sanmay and Lavoie, Allen and Magdon-Ismail, Malik and Naamad, Yonatan},
  booktitle={AAAI},
  year={2013}
}

@article{BCV13tensors,
  author    = {Aditya Bhaskara and Moses Charikar and Aravindan Vijayaraghavan},
  title     = {Uniqueness of Tensor Decompositions with Applications to
               Polynomial Identifiability},
  journal   = {CoRR},
  volume    = {abs/1304.8087},
  year      = {2013},
  ee        = {http://arxiv.org/abs/1304.8087},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@INPROCEEDINGS{AMS12,
  AUTHOR = {N. Alon and A. Moitra and B Sudakov},
  TITLE = {Nearly Complete Graphs Decomposable into Large Induced Matchings and Their Applications},
  BOOKTITLE = {Journal of the European Mathematical Society},
  YEAR = {2013},
  note = {Previous version in STOC 2012}
}

@INPROCEEDINGS{AGH13,
  AUTHOR = {Sanjeev Arora and Rong Ge and Yoni Halpern and David Mimno and Ankur Moitra and David Sontag and Yichen Wu and Michael Zhu},
  TITLE = {A Practical Algorithm for Topic Modeling with Provable Guarantees},
  BOOKTITLE = {ICML},
  YEAR = {2013},
}

@INPROCEEDINGS{BM13,
  AUTHOR = {Mark Braverman and Ankur Moitra},
  TITLE = {An Information Complexity Approach to Extended Formulations},
  BOOKTITLE = {STOC},
  YEAR = {2013},
}

@INPROCEEDINGS{HM13,
  AUTHOR = {Moritz Hardt and Ankur Moitra},
  TITLE = {Algorithms and Hardness for Robust Subspace Detection},
  BOOKTITLE = {COLT},
  YEAR = {2013},
}

@INPROCEEDINGS{M13,
  AUTHOR = {Ankur Moitra},
  TITLE = {An Almost Optimal Algorithm for Computing Nonnegative Rank},
  BOOKTITLE = {SODA},
  YEAR = {2013},
}

@INPROCEEDINGS{MO13,
  AUTHOR = {Ankur Moitra and Ryan O'Donnell},
  TITLE = {Pareto Optimal Solutions for Smoothed Analysts},
  BOOKTITLE = {SIAM Journal on Computing Special Issue for STOC 2011},
  YEAR = {2013},
}

@unpublished{Dru:prelim,
author = {Andrew Drucker},
title = {Nondeterministic Direct Product Reductions and the Success Probability of SAT Solvers},
year = {2013},
note = {To appear in FOCS 2013},
}




%Manor

@unpublished {MN-expander-random,
    AUTHOR = {Mendel, M. and Naor, A.},
     TITLE = {Expanders with respect to {H}adamard spaces and random graphs},
Note = {Preprint, submitted for publication.},
      YEAR = {2013},
      eprint={1306.5434}
}

@article{MN-calculus,
  author    = {Manor Mendel and
               Assaf Naor},
  title     = {NONLINEAR SPECTRAL CALCULUS AND SUPER-EXPANDERS},
  year      = {2013},
  eprint    = {1207.4705},
  journal= { Inst. Hautes \'{E}tudes Sci. Publ. Math},
  note ={To appear}
}



%Jelani

@unpublished{BN13,
  author = {Jean Bourgain and Jelani Nelson},
  title = {Dimensionality reduction for subsets of $\ell_2$ via sparse random matrices},
  note = {In preparation},
  year = {2013},
}

@inproceedings{NN13a,
  author = {Jelani Nelson and Huy L. Nguyen},
  title = {Sparsity lower bounds for dimensionality-reducing maps},
  booktitle = {Proceedings of the 45th ACM Symposium on Theory of Computing (STOC)},
  year = {2013}
}

@inproceedings{NN13c,
  author    = {Jelani Nelson and Huy L. Nguyen},
  title     = {OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings},
  booktitle = {Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS)},
  year      = {2013},
}

@unpublished{NN13b,
  author = {Jelani Nelson and Huy L. Nguyen},
  title = {Lower bounds for oblivious subspace embeddings},
  note = {In submission},
  year = {2013}
}

@article{KTW-StAR,
  author    = {Subhash Khot and
               Madhur Tulsiani and
               Pratik Worah},
  title     = {A Characterization of Strong Approximation Resistance},
  journal   = {Electronic Colloquium on Computational Complexity (ECCC)},
  volume    = {20},
  year      = {2013},
  pages     = {75},
  ee        = {http://eccc.hpi-web.de/report/2013/075},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{AustrinKhot-PR,
  author    = {Per Austrin and
               Subhash Khot},
  title     = {A characterization of approximation resistance for even
               k-partite {CSP}s},
  booktitle = {ITCS},
  year      = {2013},
  pages     = {187-196},
  ee        = {http://doi.acm.org/10.1145/2422436.2422459},

}

@article{KhotSaket-GHC, 
  author = {Subhash Khot and Rishi Saket},
  title = {Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs},
  journal = {Manuscript}, 
  year = {2013}
} 

@UNPUBLISHED{huang:distar,
  AUTHOR = {Hao Huang},
  TITLE = {On the maximum induced density of directed stars},
  NOTE = {submitted},
  YEAR = {2013},
}

@article{2BGPW13,
	Author = {Mark Braverman and Ankit Garg and Denis Pankratov and Omri Weinstein},
	Date-Added = {2013-07-10 17:12:11 +0000},
	Date-Modified = {2013-07-10 17:12:48 +0000},
	Journal = {CSR},
	Title = {Information lower bounds via self-reducibility },
	Year = {2013}}

@article{BGPW13,
	Author = {Mark Braverman and Ankit Garg and Denis Pankratov and Omri Weinstein},
	Date-Added = {2013-07-10 17:10:53 +0000},
	Date-Modified = {2013-07-10 17:12:04 +0000},
	Journal = {STOC },
	Title = {From Information to Exact Communication},
	Year = {2013}}

@inproceedings{BRWY13,
  author    = {Mark Braverman and
               Anup Rao and
               Omri Weinstein and
               Amir Yehudayoff},
  title     = {Direct Product via Round-Preserving Compression},
  booktitle = {ICALP (1)},
  year      = {2013},
  pages     = {232-243},
  ee        = {http://dx.doi.org/10.1007/978-3-642-39206-1_20},
}

@article{adfht,
  author = {Eric Allender and George Davie and Luke Friedman and Samuel B. Hopkins and Iddo Tzameret},
  title = {Kolmogorov complexity, circuits, and the strength of formal theories of arithmetic},	
journal={Chicago Journal of Theoretical Computer Science},
         volume={2013},
         year={2013},
	 number={5},
	 month={April},
}

@article{treewidth,
  author = {Eric Allender and Shiteng Chen and Tiancheng Lou and Periklis Papakonstantinou and Bangsheng 
Tang},
  title = {Width-parameterized {SAT}: time-space tradeoffs},
journal={Theory of Computing},
  year = {2013},
  note = {To appear}
}

@ARTICLE{limitsk.journal,
  author = {Eric Allender and Luke Friedman and William Gasarch},
  title = {Limits on the Computational Power of Random Strings},
  journal = {Information and Computation},
  volume    = {222},
  year      = {2013},
  pages     = {80-92},
}

@InCollection{alr,
  author = 	 {Eric Allender and Michelle Loui and Kenneth R. Regan},
  title = 	 {Complexity Theory},
  booktitle = 	 {Computing Handbook, 3rd Edition -- Computer Science and Software Engineering (Volume 1)},
  publisher = 	 {Chapman and Hall/CRC Press},
  note = "To appear",
  year = 	 2013,
  editor =	 {Teofilo Gonzalez},
}

@ARTICLE{aam,
    author = "Eric Allender and V. Arvind and Meena Mahajan",
    title = "Comments on Arithmetic Complexity, Kleene Closure, and Formal Power Series",
  year = {2013},
  journal = {Theory of Computing Systems},
  volume    = {53},
  pages     = {503-506},
}

@INPROCEEDINGS{fx,
  author = {Luke Friedman and Yixin Xu},
  title = {Exponential Lower Bounds for Refuting Random Formulas Using Ordered Binary Decision Diagrams},
  booktitle = {Proc. International Computer Science Symposium in Russia (CSR)},
  year = {2013},
  series = {LNCS},
  publisher = {Springer},
  note = "To appear",
}

@INPROCEEDINGS{biswas.proc,
  author = {Eric Allender},
  title = {Investigations Concerning the Structure of Complete Sets},
  booktitle = {Proc. Workshop on Complexity and Logic (in celebration of the 60th birthday of Somenath Biswas)},
  note = "To appear",
  year = {2013},
}


%sanjeev


% This file was created with JabRef 2.9.2.
% Encoding: GBK

@INPROCEEDINGS{AGHK13,
  author = {Anima Anandkumar and Rong Ge and Daniel Hsu and Sham M. Kakade},
  title = {A Tensor Approach to Learning Mixed Membership Community Models},
  booktitle = {COLT},
  year = {2013}
}

@INPROCEEDINGS{SSEFlow,
  author = {Arora, Sanjeev and Ge, Rong and Ali Kemal Sinop},
  title = {Towards a better approximation for sparsest cut?},
  booktitle = {to appear in FOCS 2013},
  year = {2013},
  owner = {gewor_000},
  timestamp = {2013.07.10}
}

@INPROCEEDINGS{SachdevaS13, 
author={Sachdeva, Sushant and Saket, Rishi}, 
booktitle={IEEE Conference on Computational Complexity (CCC}, 
title={Optimal Inapproximability for Scheduling Problems via Structural Hardness for Hypergraph Vertex Cover}, 
year={2013}, 
pages={219-229}, 
}

@ARTICLE{HatamiST13,
   author = {{Hatami}, Pooya and {Sachdeva}, Suchant and {Tulsiani}, Madhur},
    title = {An Arithmetic Analogue of {F}ox's Triangle Removal Argument},
     year = 2013,
  journal   = {Submitted to Theory of Computing},
}

@article{SachdevaV13,
  author    = {Sushant Sachdeva and
               Nisheeth K. Vishnoi},
  title     = {Matrix Inversion Is As Easy As Exponentiation},
  journal   = {CoRR},
  volume    = {abs/1305.0526},
  year      = {2013},
  ee        = {http://arxiv.org/abs/1305.0526},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}



%Avi

@inproceedings{RSW13,
  author = {Guy Rothblum and Salil Vadhan and Avi Wigderson},
  title = {Interactive Proofs of Proximity: Delegating Computation in Sublinear Time},
  booktitle = {FOCS},
  year = {2013},
}

%Bernard et al.

@unpublished{bkkm13,
title = {Constant rate {PCP}s for Circuit-{SAT} with sublinear query complexity},
author = {Eli Ben-Sasson and Yohay Kaplan and Swastik Kopparty and Or Meir},
year = {2013},
note = {To appear in FOCS '13}
}

@inproceedings{DBLP:conf/stoc/KolR13,
  author    = {Gillat Kol and Ran Raz},
  title     = {Interactive channel capacity},
  booktitle = {STOC},
  year      = {2013},
  pages     = {715-724},
  ee        = {http://doi.acm.org/10.1145/2488608.2488699},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DBLP:conf/stoc/KalaiRR13,
  author    = {Yael Tauman Kalai and Ran Raz and Ron D. Rothblum},
  title     = {Delegation for bounded space},
  booktitle = {STOC},
  year      = {2013},
  pages     = {565-574},
  ee        = {http://doi.acm.org/10.1145/2488608.2488679},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{CL12b,
  AUTHOR = {M. Charikar and S. Li},
  TITLE = {A Dependent LP-rounding Approach for the $k$-Median Problem},
  booktitle = {ICALP 2012},
  YEAR = {2012},
}

@inproceedings{DBLP:conf/nips/HardtLM12,
  author    = {Moritz Hardt and
               Katrina Ligett and
               Frank McSherry},
  title     = {A Simple and Practical Algorithm for Differentially Private
               Data Release},
  booktitle = {NIPS},
  year      = {2012},
  pages     = {2348-2356},
  ee        = {http://books.nips.cc/papers/files/nips25/NIPS2012_1143.pdf},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DBLP:conf/innovations/DworkHPRZ12,
  author    = {Cynthia Dwork and
               Moritz Hardt and
               Toniann Pitassi and
               Omer Reingold and
               Richard S. Zemel},
  title     = {Fairness through awareness},
  booktitle = {ITCS},
  year      = {2012},
  pages     = {214-226},
  ee        = {http://doi.acm.org/10.1145/2090236.2090255},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DBLP:conf/coco/RaghavendraST12,
  author    = {Prasad Raghavendra and David Steurer and Madhur Tulsiani},
  title     = {Reductions between Expansion Problems},
  booktitle = {IEEE Conference on Computational Complexity},
  year      = {2012},
  pages     = {64-73},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DL12,
  AUTHOR = {Z. Dvir and S. Lovett},
  TITLE = {Subspace Evasive Sets},
  BOOKTITLE = {STOC 2012},
  YEAR = {2012},
}

@article{GLSS,
title = {A Tail Bound for Read-$k$ Families of Functions},
author = {Dmitry Gavinsky and Shachar Lovett and Michael Saks and Srikanth Srinivasan},
journal = {Manuscript},
Year = {2012}
}

@inproceedings{DBLP:conf/approx/AroraBMS12,
  author    = {Sanjeev Arora and
               Arnab Bhattacharyya and
               Rajsekar Manokaran and
               Sushant Sachdeva},
  title     = {Testing Permanent Oracles - Revisited},
  booktitle = {APPROX-RANDOM},
  year      = {2012},
  pages     = {362-373},
  ee        = {http://dx.doi.org/10.1007/978-3-642-32512-0_31},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{AN12,
  author = {Alexandr Andoni and Huy L. Nguyen},
  title = {Width of Points in the Streaming Model},
  year = {2012},
  booktitle = {SODA},
  pages = {447-452}
}

@article{DBLP:journals/siamcomp/AgarwalAKMTY12,
  author    = {Pankaj K. Agarwal and Lars Arge and Haim Kaplan and Eyal Molad and Robert Endre Tarjan and Ke Yi},
  title     = {An Optimal Dynamic Data Structure for Stabbing-Semigroup Queries},
  journal   = {SIAM J. Comput.},
  volume    = {41},
  number    = {1},
  year      = {2012},
  pages     = {104-127},
  ee        = {http://dx.doi.org/10.1137/10078791X},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DBLP:conf/focs/RamshawT12,
  author    = {Lyle Ramshaw and Robert Endre Tarjan},
  title     = {A Weight-Scaling Algorithm for Min-Cost Imperfect Matchings in Bipartite Graphs},
  booktitle = {FOCS},
  year      = {2012},
  pages     = {581-590},
  ee        = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2012.9},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DBLP:conf/icalp/GeorgiadisT12,
  author    = {Loukas Georgiadis and Robert Endre Tarjan},
  title     = {Dominators, Directed Bipolar Orders, and Independent Spanning Trees},
  booktitle = {ICALP (1)},
  year      = {2012},
  pages     = {375-386},
  ee        = {http://dx.doi.org/10.1007/978-3-642-31594-7_32},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@Article{commensal2012,
  title =	"Commensal cuckoo: secure group partitioning for
		 large-scale services",
  author =	"Siddhartha Sen and Michael J. Freedman",
  journal =	"Operating Systems Review",
  year = 	"2012",
  number =	"1",
  volume =	"46",
  pages =	"33--39",
}

@inproceedings{DBLP:conf/stoc/BrodalLT12,
  author    = {Gerth St{\o}lting Brodal and George Lagogiannis and Robert Endre Tarjan},
  title     = {Strict {F}ibonacci heaps},
  booktitle = {STOC},
  year      = {2012},
  pages     = {1177-1184},
  ee        = {http://doi.acm.org/10.1145/2213977.2214082},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DBLP:conf/wdag/AfekKKMT12,
  author    = {Yehuda Afek and Haim Kaplan and Boris Korenfeld and Adam Morrison and Robert Endre Tarjan},
  title     = {CBTree: A Practical Concurrent Self-Adjusting Search Tree},
  booktitle = {DISC},
  year      = {2012},
  pages     = {1-15},
  ee        = {http://dx.doi.org/10.1007/978-3-642-33651-5_1},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@Article{HaeuplerKMST2011,
  title =   "Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance",
  author =	"Bernhard Haeupler and Telikepalli Kavitha and Rogers Mathew and Siddhartha Sen and Robert Endre Tarjan",
  journal =	"ACM Trans. Alg.",
  volume = {8},
  number = {1},
  year = {2012},
  pages = {3:1--3:33}
}

@article{DBLP:journals/corr/abs-1205-2740,
  author    = {Mangesh Gupte and
               Darja Krushevskaja and
               S. Muthukrishnan},
  title     = {Analyses of Cardinal Auctions},
  journal   = {CoRR},
  volume    = {abs/1205.2740},
  year      = {2012},
  ee        = {http://arxiv.org/abs/1205.2740},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{KhotNaor-GrothendieckSurvey,
author ="S. Khot and A. Naor",
title = "Grothendieck-type Inequalities in Combinatorial Optimization", 
journal ="Communications in Pure and Applied Mathematics", 
year = "2012"
}

@inproceedings{KhotPopatVishnoi,
author = "S. Khot and P. Popat and N. Vishnoi", title = "$2^{\log^{1-\epsilon} n}$ Hardness for Closest Vector Problem with Preprocessing",
booktitle = "STOC", 
year = "2012"
}

@article{DBLP:journals/cpc/Naor12,
  author    = {Assaf Naor},
  title     = {On the Banach-Space-Valued Azuma Inequality and Small-Set Isoperimetry of Alon-Roichman Graphs},
  journal   = {Combinatorics, Probability {\&} Computing},
  volume    = {21},
  number    = {4},
  year      = {2012},
  pages     = {623-634},
  ee        = {http://dx.doi.org/10.1017/S0963548311000757},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{HeilmanJN12,
  author    = {Steven Heilman and Aukosh Jagannath and Assaf Naor},
  title     = {Solution of the propeller conjecture in {R}$^{\mbox{3}}$},
  booktitle = {STOC},
  year      = {2012},
  pages     = {269-276},
}

@inproceedings{DBLP:conf/sigecom/AroraGSS12,
  author    = {Sanjeev Arora and
               Rong Ge and
               Sushant Sachdeva and
               Grant Schoenebeck},
  title     = {Finding overlapping communities in social networks: toward
               a rigorous approach},
  booktitle = {Electronic Commerce},
  year      = {2012},
  pages     = {37-54},
  ee        = {http://doi.acm.org/10.1145/2229012.2229020},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@INPROCEEDINGS{CCE12,
  AUTHOR = {J. Chuzhoy and P. Charlermsook and A. Ene and S. Li},
  TITLE = {Approximation Algorithms and Hardness of Integral Concurrent Flow},
  BOOKTITLE = {STOC 2012},
  YEAR = {2012},
}

@article{MMV,
  author    = {Konstantin Makarychev and Yury Makarychev and
               Aravindan Vijayaraghavan},
  title     = {Approximation Algorithms for Semi-random Partitioning problems},
 journal = {STOC},
  year = {2012}
}

@inproceedings{LN12blah,
  author = {Kasper Green Larsen and Huy L. Nguyen},
  title = {Improved Range Searching Lower Bounds},
  year = {2012},
  booktitle = {SoCG},
}

@inproceedings{BIS12,
  author    = {Paul Beame and Russell Impagliazzo and Srikanth Srinivasan},
  title     = {Approximating $AC^0$ by Small Height Decision Trees and a
               Deterministic Algorithm for $AC^0$SAT},
  booktitle = {IEEE Conference on Computational Complexity},
  year      = {2012},
  pages     = {117-125},
}

@article{MO12,
  author    = {Ankur Moitra and Ryan O'Donnell},
  title     = {Pareto Optimal Solutions for Smoothed Analysts},
  journal   = {SIAM J. Comput.},
  volume    = {41},
  number    = {5},
  year      = {2012},
  pages     = {1266-1284},
}

@inproceedings{KOTYZ12,
  author    = {G{\'a}bor Kun and Ryan O'Donnell and Suguru Tamaki and Yuichi Yoshida and Yuan Zhou},
  title     = {Linear programming, width-1 {CSP}s, and robust satisfaction},
  booktitle = {ITCS},
  year      = {2012},
  pages     = {484-495},
  ee        = {http://doi.acm.org/10.1145/2090236.2090274},
}

@inproceedings{LovettMeka12,
    title = {Constructive Discrepancy Minimization by Walking on The Edges},
    booktitle = {FOCS},
    author = {Shachar Lovett and Raghu Meka},
    year={2012},
}

@inproceedings{DBLP:conf/focs/Meka12,
  author    = {Raghu Meka},
  title     = {A PTAS for Computing the Supremum of {G}aussian Processes},
  booktitle = {FOCS},
  year      = {2012},
  pages     = {217-222},
  ee        = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2012.24},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@UNPUBLISHED{LLVK,
  AUTHOR = {L. Lov\'asz and K. Vesztergombi},
  TITLE = {Nondeterministic graph property testing},
  NOTE = {Manuscript},
  YEAR = {2012},
  URL = {http://arxiv.org/abs/1202.5337}
}

@inproceedings{KuperbergLovettPeled12,
    title = {Probabilistic existence of rigid combinatorial objects},
    booktitle = {STOC},
    author = {Greg Kuperberg and Shachar Lovett and Ron Peled},
    year={2012},
}

@INPROCEEDINGS{KMV12,
  AUTHOR = {A. Kalai and A. Moitra and G. Valiant},
  TITLE = {Disentangling {G}aussians},
  BOOKTITLE = {Communications of the ACM (CACM), Research Highlights, February 2012},
  YEAR = {2012},
}

@article{IMZ12,
  author    = {Russell Impaliazzo and Raghu Meka and David Zuckerman},
  title     = {Pseudorandomness from Shrinkage},
  journal   = {Electronic Colloquium on Computational Complexity (ECCC)},
  volume    = {19},
  number = {57},
  year      = {2012},
  ee        = {http://eccc.hpi-web.de/report/2012/057},
}

@inproceedings{Impagliazzo:2012:SAA:2095116.2095193,
 author = {Impagliazzo, Russell and Matthews, William and Paturi, Ramamohan},
 title = {A satisfiability algorithm for AC0},
 booktitle = {Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms},
 series = {SODA '12},
 year = {2012},
 location = {Kyoto, Japan},
 pages = {961--972},
 numpages = {12},
 url = {http://dl.acm.org/citation.cfm?id=2095116.2095193},
 acmid = {2095193},
 publisher = {SIAM},
}

@UNPUBLISHED{DKL12,
  AUTHOR = {Z. Dvir and J. Koll\'{a}r and S. Lovett},
  TITLE = {Variety Evasive Sets},
  YEAR = {2012},
  NOTE = {To appear in Computational Complexity (journal).  arXiv:1203.4532}
}

@inproceedings{DKS12,
  author    = {Amit Deshpande and Ravindran Kannan and Nikhil Srivastava},
  title     = {Zero-One Rounding of Singular Vectors},
  booktitle = {ICALP (1)},
  year      = {2012},
  pages     = {278-289},
}

@inproceedings{HST12,
  author    = {Moritz Hardt and Nikhil Srivastava and Madhur Tulsiani},
  title     = {Graph densification},
  booktitle = {ITCS},
  year      = {2012},
  pages     = {380-392},
}

@inproceedings{AlonLovett11,
    author = {Noga Alon and Shachar Lovett},
    title = {Almost k-wise vs k-wise independent permutations, and uniformity for general group actions},
    year = {2012},
    booktitle = {16th RANDOM},
}

@inproceedings{DBLP:conf/focs/BeckIL12,
  author    = {Chris Beck and
               Russell Impagliazzo and
               Shachar Lovett},
  title     = {Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-Circuits},
  booktitle = {FOCS},
  year      = {2012},
  pages     = {101-110},
  ee        = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2012.82},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{BCGVZ,
  author    = {Aditya Bhaskara and Moses Charikar and Venkatesan Guruswami and
               Aravindan Vijayaraghavan and Yuan Zhou},
  title     = {Polynomial Integrality gaps for strong {SDP} relaxations of Densest $k$-subgraph},
  booktitle = {SODA},	
  year = {2012}
}

@InProceedings{CMVZ,
  author    = {Julia Chuzhoy and Yury Makarychev  and
               Aravindan Vijayaraghavan and Yuan Zhou},
  title     = {Approximation algorithms and Hardness for the $k$-route cut problem},
 booktitle = {SODA},
  year = {2012}
}

@INPROCEEDINGS{QPR,
  AUTHOR = {Aditya Bhaskara and Moses Charikar and Rajsekar Manokaran and Aravindan Vijayaraghavan},
  TITLE = {On Quadratic Programming with a Ratio Objective},
  BOOKTITLE = {ICALP (1) 2012},
  YEAR = {2012},
}

@inproceedings{DBLP:conf/stoc/BeameBI12,
  author    = {Paul Beame and
               Christopher Beck and
               Russell Impagliazzo},
  title     = {Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space},
  booktitle = {STOC},
  year      = {2012},
  pages     = {213-232},
  ee        = {http://doi.acm.org/10.1145/2213977.2213999},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@unpublished{ADSW12,
  author = {Albert Ai and Zeev Dvir and Shubhangi Saraf and Avi Wigderson},
  title = {{{S}ylvester-{G}allai theorems for approximate collinearity}},
  note = {Manuscript},
  year = {2012},
}

@inproceedings{BKS12,
  author    = {Jan Bul{\'a}nek and
               Michal Kouck{\'y} and
               Michael Saks},
  title     = {Tight lower bounds for the online labeling problem},
  booktitle = {STOC},
  year      = {2012},
}

@inproceedings{BBCKS12,
  author    = {Martin Babka and Jan Bul{\'a}nek and Vincent Cun{\'a}t and
               Michal Kouck{\'y} and
               Michael Saks},
  title     = {On online labeling with polynomially many labels},
 booktitle = {European Symposium on Algorithms (ESA)},
  year      = {2012},
}
 

@inproceedings{DMPY12,
  AUTHOR = {Z. Dvir and G. Malod and S. Perifel and A. Yehudayoff},
  TITLE = {Separating multilinear branching programs and formulas},
  BOOKTITLE = {STOC 2012},
  YEAR = {2012},
}

@inproceedings{DBLP:conf/sigecom/CaragiannisESY12,
  author    = {Ioannis Caragiannis and
               Edith Elkind and
               Mario Szegedy and
               Lan Yu},
  title     = {Mechanism design: from partial to probabilistic verification},
  booktitle = {ACM Conference on Electronic Commerce},
  year      = {2012},
  pages     = {266-283},
  ee        = {http://doi.acm.org/10.1145/2229012.2229035},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@INPROCEEDINGS{cesy12,
  author = {Magnus M. Halldorsson, Xiaoming Sun, Mario Szegedy and Chengu Wang},
  title = {Streaming and Communication Complexity of Clique Approximation},
  booktitle = {ICALP (1)},
  year = {2012},
}

@inproceedings{DBLP:conf/approx/KolipakaSX12,
  author    = {Kashyap Babu Rao Kolipaka and
               Mario Szegedy and
               Yixin Xu},
  title     = {A Sharper Local Lemma with Improved Applications},
  booktitle = {APPROX-RANDOM},
  year      = {2012},
  pages     = {603-614},
  ee        = {http://dx.doi.org/10.1007/978-3-642-32512-0_51},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{SS,
title = {On the Limits of Sparsification},
author = {Rahul Santhanam and
Srikanth Srinivasan},
Booktitle = {ICALP (1)},
Year = {2012}
}

@inproceedings{OSV12,
  author    = {Lorenzo Orecchia and
               Sushant Sachdeva and
               Nisheeth K. Vishnoi},
  title     = {Approximating the Exponential, the Lanczos Method and an $\tilde{O}(m)$-Time Spectral Algorithm for Balanced Separator},
 booktitle   = {STOC},
  year      = {2012},
}

@inproceedings{RR12,
    AUTHOR = {Raz, Ran and Ricky Rosen},
     TITLE = {A Strong Parallel Repetition Theorem
for Projection Games on Expanders},
   booktitle = {Conference on Computational Complexity (CCC)},
    year = {2012},
}

@inproceedings{RothS12,
author = {Aaron Roth and Grant Schoenebeck},
title = {Conducting Truthful Surveys, Cheaply},
booktitle = "Proceedings of the 13th ACM conference on Electronic commerce (EC 2012)",
year = {2012},
}

@inproceedings{RamshawT2012,
 author = {Ramshaw, Lyle and Tarjan, Robert E.},
 title = {A Weight-Scaling Algorithm for Min-Cost Imperfect Matchings in Bipartite Graphs},
 booktitle = {FOCS},
 year = {2012},
 pages = {581--590},
} 

@inproceedings{AfekKKMT2012,
 author = {Afek, Yehuda and Kaplan, Haim and Korenfeld, Boris and Morrison, Adam and Tarjan, Robert E.},
 title = {{CBTree}: a practical concurrent self-adjusting search tree},
 booktitle = {International Conference on Distributed Computing (DISC)},
 year = {2012},
 pages = {1--15},
} 

@inproceedings{GeorgiadisT2012,
 author = {Georgiadis, Loukas and Tarjan, Robert E.},
 title = {Dominators, directed bipolar orders, and independent spanning trees},
 booktitle = {International Colloquium on Automata, Languages, and Programming (ICALP)},
 year = {2012},
 pages = {375--386},
}

@inproceedings{JaffeST2012,
 author = {Jaffe, Alexander and Moscibroda, Thomas and Sen, Siddhartha},
 title = {On the price of equivocation in byzantine agreement},
 booktitle = {ACM Symposium on Principles of Distributed Computing (PODC)},
 year = {2012},
 pages = {309--318},
}

@article{Sen2012,
 author = {Sen, Siddhartha},
 title = {Review of {PODC} 2012},
 journal = {SIGACT News},
 volume = {43},
 number = {4},
 year = {2012},
 pages = {104--111},
} 

@INPROCEEDINGS{CL12,
  AUTHOR = {J. Chuzhoy and S. Li},
  TITLE = {A Polylogarithimic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2},
  BOOKTITLE = {FOCS},
  YEAR = {2012},
}

@inproceedings{BDKT,
  author    = {Aditya Bhaskara and
               Daniel Dadush and
               Ravishankar Krishnaswamy and
               Kunal Talwar},
  title     = {Unconditional Differentially Private Mechanisms for Linear Queries},
  booktitle = {STOC},
  year      = {2012},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DBLP:conf/approx/BhaskaraDS12,
  author    = {Aditya Bhaskara and
               Devendra Desai and
               Srikanth Srinivasan},
  title     = {Optimal Hitting Sets for Combinatorial Shapes},
  booktitle = {APPROX-RANDOM},
  year      = {2012},
  pages     = {423-434},
  ee        = {http://dx.doi.org/10.1007/978-3-642-32512-0_36},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@INPROCEEDINGS{AGMS12,
  AUTHOR = {Sanjeev Arora and Rong Ge and Ankur Moitra and Suchant Sachdeva},
  TITLE = {Provable {ICA} with Unknown {G}aussian Noise, and Implications for {G}aussian Mixtures and Autoencoders},
  BOOKTITLE = {NIPS},
  YEAR = {2012},
}

@inproceedings{DBLP:conf/focs/WigdersonY12,
  author    = {Avi Wigderson and
               Amir Yehudayoff},
  title     = {Population Recovery and Partial Identification},
  booktitle = {FOCS},
  year      = {2012},
  pages     = {390-399},
  ee        = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2012.14},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article {MN-cat0-extension,
    AUTHOR = {Mendel, M. and Naor, A.},
     TITLE = {Spectral calculus and {L}ipschitz extension for barycentric metric spaces},
   JOURNAL = {Anal. Geom. Metr. Spaces},
    VOLUME = {1},
      YEAR = {2012},
     PAGES = {163--199},
     eprint={1301.3963},
}

@article{N12,
  author    = {Jelani Nelson},
  title     = {Sketching and streaming algorithms for processing massive data},
  journal   = {ACM Crossroads},
  volume    = {19},
  number    = {1},
  year      = {2012},
  pages     = {14--19},
}

@inproceedings{NNW12,
  author    = {Jelani Nelson and Huy L. Nguyen and David P. Woodruff},
  title     = {On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation},
  booktitle = {RANDOM},
  year      = {2012},
  pages     = {627--638},
}

@article{NPW12,
  author    = {Jelani Nelson and Eric Price and Mary Wootters},
  title     = {New constructions of RIP matrices with fast multiplication and fewer rows},
  journal   = {CoRR},
  volume    = {abs/1211.0986},
  year      = {2012},
}


%Subhash

@article{KTW-SoAR,
  author    = {Subhash Khot and
               Madhur Tulsiani and
               Pratik Worah},
  title     = {The Complexity of Somewhat Approximation Resistant Predicates},
  journal   = {Electronic Colloquium on Computational Complexity (ECCC)},
  volume    = {19},
  year      = {2012},
  pages     = {151},
  ee        = {http://eccc.hpi-web.de/report/2012/151},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@unpublished{LN12,
    author={Li, S. and Naor, A.},
    title = {Discretization and affine approximation ih high dimensions},
    note={Submitted for publication.  http://arxiv.org/abs/1202.2567},
    year= {2012},
}

@inproceedings{PW12,
author = "P. Popat and Y. Wu",
title = "On the Hardness of Pricing Loss-leaders", booktitle = "SODA", year = "2012"
}


%Hao

@UNPUBLISHED{cli-ind,
  AUTHOR = {Hao Huang and Nathan Linial and Humberto Naves and Yuval Peled and Benny Sudakov},
  TITLE = {On the densities of cliques and independent sets in graphs},
  NOTE = {submitted},
  YEAR = {2012},

}

@UNPUBLISHED{3-local,
  AUTHOR = {Hao Huang and Nathan Linial and Humberto Naves and Yuval Peled and Benny Sudakov},
  TITLE = {On the $3$-local profiles of graphs},
  NOTE = {submitted},
  YEAR = {2012},

}

%Braverman-group

%% This BibTeX bibliography file was created using BibDesk.
%% http://bibdesk.sourceforge.net/


%% Created for Ankit Garg at 2013-07-10 13:12:48 -0400 


%% Saved with string encoding Unicode (UTF-8) 

@article{BRWY12,
  author    = {Mark Braverman and
               Anup Rao and
               Omri Weinstein and
               Amir Yehudayoff},
  title     = {Direct Products in Communication Complexity},
  journal   = {Electronic Colloquium on Computational Complexity (ECCC)},
  volume    = {19},
  year      = {2012},
  pages     = {143},
  ee        = {http://eccc.hpi-web.de/report/2012/143},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


%Eric

@INPROCEEDINGS{cie12,
  author = {Eric Allender},
  title = {Curiouser and Curiouser: The Link between Incompressibility and Complexity},
  booktitle = {Proc. Computability in Europe (CiE)},
  series = {LNCS},
  publisher = {Springer},
volume    = {7318},
  year      = {2012},
 pages     = {11-16},
}

@ARTICLE{pathetic,
    author = "Eric Allender and V. Arvind and Rahul Santhanam and Fengming Wang",
    title = "Uniform Derandomization from Pathetic Lower Bounds",
  year = {2012},
  journal = {Philosophical Transactions of the Royal Society, Series A},
  volume    = {370},
  pages     = {3512-3535},
  note = {Earlier version in RANDOM '10}
}

@INPROCEEDINGS{abfl,
  author = {Eric Allender and Harry Buhrman and Luke Friedman and Bruno Loff},
  title = {Reductions to the set of random strings: The resource-bounded case},
  booktitle = {Proc. Symposium on Mathematical Foundations of Computer Science (MFCS '12)},
  year = {2012},
  series = {LNCS},
  publisher = {Springer},
volume    = {7464},
 pages     = {88-99},
}

@ARTICLE{AGHKT12,
  author = {A. Anandkumar and R. Ge and D. Hsu and S. M. Kakade and M. Telgarsky},
  title = {Tensor Decompositions for Latent Variable Models},
  journal = {CoRR},
  year = {2012},
  volume = {abs/1210.7559},
}

@INPROCEEDINGS{NMF,
  author = {Sanjeev Arora and Rong Ge and Ravindran Kannan and Ankur Moitra},
  title = {Computing a Nonnegative Matrix Factorization \--- Provably},
  booktitle = {STOC},
  year = {2012},
  pages = {145-162},
}

@INPROCEEDINGS{TopicModel,
  author = {Arora, Sanjeev and Ge, Rong and Moitra, Ankur},
  title = {Learning Topic Models \--- Going Beyond {SVD}},
  booktitle = {FOCS},
  year = {2012},
  pages = {1-10},
}

@article{Barak_Goldreich_Impagliazzo_Rudich_Sahai_Vadhan_Yang_2001,
title={On the (Im)possibility of Obfuscating Programs},
volume={59},
number={2},
journal={Journal of the ACM},
author={Barak, Boaz and Goldreich, Oded and Impagliazzo, Russell and Rudich, Steven and Sahai, Amit and Vadhan, Salil and Yang, Ke},
year={2012},
article={6},
}

@InProceedings{localflow2012,
  title = "LocalFlow: Scalable, Optimal Flow Routing in Datacenters",
  author = "Siddhartha Sen and David Shue and Sunghwan Ihm and Michael J. Freedman",
  booktitle = "ACM Special Interest Group on Data Communication",
  note = "Submitted",
  year = 2012,
}

@UNPUBLISHED{SV,
  AUTHOR = {Nikhil Srivastava and Roman Vershynin},
  TITLE = {Covariance Estimation for Distributions with $2+\epsilon$ Moments},
  NOTE = {To appear in {\em Annals of Probability}},
  YEAR = {2012}
}

@article{SchoenebeckV12,
 author = {Grant Schoenebeck and Salil Vadhan},
 title = {The computational complexity of {N}ash equilibria in concisely represented games},
 journal = {ACM Transactions on the Theory of Computation},
 year = {2012},
 volume = {4},
 issue = {1},
 NOTE = "To Appear",
}

@InProceedings{greenup2012,
  title = "Don't Lose Sleep Over Availability: The {G}reen{U}p Decentralized Wakeup Service",
  author = "Siddhartha Sen and Jacob R. Lorch and Richard Hughes and Carlos G. J. Suarez and Brian Zill and Weverton Cordeiro and Jitendra Padhye",
  booktitle = "USENIX Symposium on Networked Systems Design and Implementation",
  year = 2012,
}

@unpublished{DSW12,
  author = {Zeev Dvir and Shubhangi Saraf and Avi Wigderson},
  title = {{Improved rank bounds for design matrices and a new proof of {K}elly's theorem.}},
  note = {Manuscript},
  year = {2012},
}

@INPROCEEDINGS{bc1,
  AUTHOR = {Bernard Chazelle},
  TITLE = {Natural Algorithms and Influence Systems},
  BOOKTITLE = {C.ACM 55},
  YEAR = {2012}
}

@INPROCEEDINGS{bc2,
  AUTHOR = {Bernard Chazelle},
  TITLE = { The Dynamics of Influence Systems},
  BOOKTITLE = {FOCS},
  YEAR = {2012}
}

@inproceedings{DBLP:conf/focs/Ben-SassonLR12,
  author    = {Eli Ben-Sasson and
               Shachar Lovett and
               Noga Ron-Zewi},
  title     = {An Additive Combinatorics Approach Relating Rank to Communication Complexity},
  booktitle = {FOCS},
  year      = {2012},
  pages     = {177-186},
  ee        = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2012.39},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@ARTICLE{BCLSV2,
  AUTHOR = {C. Borgs and J. Chayes and L. Lov\'asz and V.T. S\'os and K. Vesztergombi},
  TITLE = {Convergent Sequences of Dense Graphs II. Multiway Cuts and Statistical Physics},
  JOURNAL = {Annals of Mathematics},
  VOLUME = {176},
  ISSUE = {1},
  YEAR = {2012},
}

@UNPUBLISHED{HLSz,
  AUTHOR = {H. Hatami and L. Lov\'asz and B. Szegedy},
  TITLE = {Limits of local-global convergent graph sequences},
  NOTE = {Manuscript},
  YEAR = {2012},
}

@inproceedings{GLS,
title = {Pseudorandom generators of Read-Once $\mathrm{ACC}^0$},
author = {Dmitry Gavinsky and Shachar Lovett and Srikanth Srinivasan},
Booktitle = {IEEE Conference on Computational Complexity (CCC)},
Year = {2012}
}

@inproceedings{DBLP:conf/innovations/DvirGRV11,
  author    = {Zeev Dvir and
               Dan Gutfreund and
               Guy N. Rothblum and
               Salil P. Vadhan},
  title     = {On Approximating the Entropy of Polynomial Mappings},
  booktitle = {ICS},
  year      = {2011},
  pages     = {460-475},
  ee        = {http://conference.itcs.tsinghua.edu.cn/ICS2011/content/papers/28.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DBLP:conf/focs/BhattacharyyaDSS11,
  author    = {Arnab Bhattacharyya and
               Zeev Dvir and
               Amir Shpilka and
               Shubhangi Saraf},
  title     = {Tight Lower Bounds for 2-query LCCs over Finite Fields},
  booktitle = {FOCS},
  year      = {2011},
  pages     = {638-647},
  ee        = {http://dx.doi.org/10.1109/FOCS.2011.28},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{Csenergy,
 author = {B. Chazelle},
 title  = {The total s-energy of a multiagent system},
 year   = {2011},
 journal =  {SIAM Journal on Control and Optimization},
 volume = {49},
 pages = {1680-1706},
  }

@article{DBLP:journals/corr/abs-1102-1456,
  author    = {Sanjeev Arora and
               James R. Lee and
               Sushant Sachdeva},
  title     = {A Reformulation of the Arora-Rao-Vazirani Structure Theorem},
  journal   = {CoRR},
  volume    = {abs/1102.1456},
  year      = {2011},
  ee        = {http://arxiv.org/abs/1102.1456},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DBLP:conf/icalp/AroraG11,
  author    = {Sanjeev Arora and
               Rong Ge},
  title     = {New Algorithms for Learning in Presence of Errors},
  booktitle = {ICALP (1)},
  year      = {2011},
  pages     = {403-415},
  ee        = {http://dx.doi.org/10.1007/978-3-642-22006-7_34},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DBLP:conf/approx/AroraG11,
  author    = {Sanjeev Arora and
               Rong Ge},
  title     = {New Tools for Graph Coloring},
  booktitle = {APPROX-RANDOM},
  year      = {2011},
  pages     = {1-12},
  ee        = {http://dx.doi.org/10.1007/978-3-642-22935-0_1},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{DBLP:journals/cc/AlekhnovichAT11,
  author    = {Mikhail Alekhnovich and
               Sanjeev Arora and
               Iannis Tourlakis},
  title     = {Towards Strong Nonapproximability Results in the Lov{\'a}sz-Schrijver
               Hierarchy},
  journal   = {Computational Complexity},
  volume    = {20},
  number    = {4},
  year      = {2011},
  pages     = {615-648},
  ee        = {http://dx.doi.org/10.1007/s00037-011-0027-z},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{DBLP:journals/cacm/AroraBBG11,
  author    = {Sanjeev Arora and
               Boaz Barak and
               Markus Brunnermeier and
               Rong Ge},
  title     = {Computational complexity and information asymmetry in financial products},
  journal   = {Commun. ACM},
  volume    = {54},
  number    = {5},
  year      = {2011},
  pages     = {101-107},
  ee        = {http://doi.acm.org/10.1145/1941487.1941511},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DOSW:11,
  author={I. Diakonikolas and R. O'Donnell and R. Servedio and Y. Wu},
  title={Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions},
  booktitle = {SODA},
  year={2011},
  pages={1590-1606}
}

@inproceedings{FLS11:colt,
  author    = {V. Feldman and H. Lee and R. Servedio},
  title     = {Lower Bounds and Hardness Amplification for Learning
Shallow Monotone Formulas},
  booktitle = {COLT},
  year      = {2011},
  pages     = {to appear}
}

@unpublished{LS11:hamming,
  author = {P. Long and R. Servedio},
  title={{On the weight of halfspaces over Hamming balls}},
  note={Manuscript},
  year={2011}
}

@unpublished{DDS11:poisson,
  author = {C. Daskalakis and I. Diakonikolas and R. Servedio},
  title={{Learning Poisson Binomial Distributions}},
  note={Manuscript},
  year={2011}
}

@unpublished{DDS11:kmodal,
  author = {C. Daskalakis and I. Diakonikolas and R. Servedio},
  title={{Learning and testing $k$-modal distributions}},
  note={Manuscript},
  year={2011}
}

@unpublished{LS11:malicious,
  author = {P. Long and R. Servedio},
  title={{Learning large-margin halfspaces with more malicious noise}},
  note={Manuscript},
  year={2011}
}

@unpublished{DDS11:canonical,
  author = {D. Dachman-Soled and R. Servedio},
  title={{A canonical form for
testing Boolean function properties}},
  note={Manuscript},
  year={2011}
}

@article{JLSW11:dam,
  author={J. Jackson and H.K. Lee and R. Servedio and A. Wan},
  title={{Learning Random Monotone DNF}},
  journal={Discrete Applied Mathematics},
  volume={159},
  number={5},
  pages={259-271},
  year={2011}
}

@article{OS11:chow,
  author={R. O'Donnell and R. Servedio},
  title={{The Chow Parameters Problem}},
  journal={SIAM Journal on Computing},
  volume={40},
  number={1},
  pages={165-199},
  year={2011}
}

@inproceedings{DBLP:conf/stoc/GuptaHRU11,
  author    = {Anupam Gupta and
               Moritz Hardt and
               Aaron Roth and
               Jonathan Ullman},
  title     = {Privately releasing conjunctions and the statistical query
               barrier},
  booktitle = {STOC},
  year      = {2011},
  pages     = {803-812},
  ee        = {http://doi.acm.org/10.1145/1993636.1993742},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DBLP:conf/soda/KumarMTV11,
  author    = {Amit Kumar and
               Rajsekar Manokaran and
               Madhur Tulsiani and
               Nisheeth K. Vishnoi},
  title     = {On LP-Based Approximability for Strict {CSP}s},
  booktitle = {SODA},
  year      = {2011},
  pages     = {1560-1573},
  ee        = {http://www.siam.org/proceedings/soda/2011/SODA11_120_kumara.pdf},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DBLP:conf/soda/DeshpandeTV11,
  author    = {Amit Deshpande and
               Madhur Tulsiani and
               Nisheeth K. Vishnoi},
  title     = {Algorithms and Hardness for Subspace Approximation},
  booktitle = {SODA},
  year      = {2011},
  pages     = {482-496},
  ee        = {http://www.siam.org/proceedings/soda/2011/SODA11_039_deshpandea.pdf},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{TulsianiW11,
  author    = {Madhur Tulsiani and Julia Wolf},
  title     = {Quadratic Goldreich-Levin Theorems},
  booktitle = {FOCS},
  year      = {2011},
  pages     = {619-628},
  ee        = {http://dx.doi.org/10.1109/FOCS.2011.59},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DBLP:conf/infocom/BateniHJP11,
  author    = {MohammadHossein Bateni and
               Mohammad Taghi Hajiaghayi and
               Sina Jafarpour and
               Dan Pei},
  title     = {Towards an efficient algorithmic framework for pricing cellular
               data service},
  booktitle = {INFOCOM},
  year      = {2011},
  pages     = {581-585},
  ee        = {http://dx.doi.org/10.1109/INFCOM.2011.5935231},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{HS10,
author = {Thomas Hollenstein and Grant Schoenebeck},
title = {General Hardness Amplification of Predicates and Puzzles},
year = {2011},
month = "March",
booktitle = "Theory of Cryptography Conference"
}

@inproceedings{AC11,
 author = {N. Ailon and B. Chazelle and K. Clarkson and W. Mulzer and C. Seshadhri},
 title  = {Self-Improving Algorithms},
 year   = {2011},
 booktitle  =  "SIAM Journal on Computing",
    }

@article{DBLP:journals/algorithmica/CharikarHK11,
  author    = {Moses Charikar and
               MohammadTaghi Hajiaghayi and
               Howard J. Karloff},
  title     = {Improved Approximation Algorithms for Label Cover Problems},
  journal   = {Algorithmica},
  volume    = {61},
  number    = {1},
  year      = {2011},
  pages     = {190-206},
  ee        = {http://dx.doi.org/10.1007/s00453-010-9464-3},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{DBLP:journals/siamcomp/GuruswamiHMRC11,
  author    = {Venkatesan Guruswami and
               Johan H{\aa}stad and
               Rajsekar Manokaran and
               Prasad Raghavendra and
               Moses Charikar},
  title     = {Beating the Random Ordering Is Hard: Every Ordering {CSP}
               Is Approximation Resistant},
  journal   = {SIAM J. Comput.},
  volume    = {40},
  number    = {3},
  year      = {2011},
  pages     = {878-914},
  ee        = {http://dx.doi.org/10.1137/090756144},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{DBLP:journals/siamcomp/AilonC11,
  author    = {Nir Ailon and Moses Charikar},
  title     = {Fitting Tree Metrics: Hierarchical Clustering and Phylogeny},
  journal   = {SIAM J. Comput.},
  volume    = {40},
  number    = {5},
  year      = {2011},
  pages     = {1275-1291},
  ee        = {http://dx.doi.org/10.1137/100806886},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DBLP:conf/soda/BateniCEHKM11,
  author    = {MohammadHossein Bateni and
               Chandra Chekuri and
               Alina Ene and
               Mohammad Taghi Hajiaghayi and
               Nitish Korula and
               D{\'a}niel Marx},
  title     = {Prize-collecting Steiner Problems on Planar Graphs},
  booktitle = {SODA},
  year      = {2011},
  pages     = {1028-1049},
  ee        = {http://www.siam.org/proceedings/soda/2011/SODA11_078_batenim.pdf},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{DBLP:journals/siamcomp/ArcherBHK11,
  author    = {Aaron Archer and
               MohammadHossein Bateni and
               MohammadTaghi Hajiaghayi and
               Howard J. Karloff},
  title     = {Improved Approximation Algorithms for Prize-Collecting Steiner
               Tree and TSP},
  journal   = {SIAM J. Comput.},
  volume    = {40},
  number    = {2},
  year      = {2011},
  pages     = {309-332},
  ee        = {http://dx.doi.org/10.1137/090771429},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DBLP:conf/focs/AndoniCNN11,
  author    = {Alexandr Andoni and
               Moses Charikar and
               Ofer Neiman and
               Huy L. Nguyen},
  title     = {Near Linear Lower Bound for Dimension Reduction in L1},
  booktitle = {FOCS},
  year      = {2011},
  pages     = {315-323},
  ee        = {http://dx.doi.org/10.1109/FOCS.2011.87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DBLP:conf/soda/CharikarNN11,
  author    = {Moses Charikar and
               Alantha Newman and
               Aleksandar Nikolov},
  title     = {Tight Hardness Results for Minimizing Discrepancy},
  booktitle = {SODA},
  year      = {2011},
  pages     = {1607-1614},
  ee        = {http://www.siam.org/proceedings/soda/2011/SODA11_123_charikarm.pdf},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DBLP:conf/www/DongCL11,
  author    = {Wei Dong and
               Moses Charikar and
               Kai Li},
  title     = {Efficient k-nearest neighbor graph construction for generic
               similarity measures},
  booktitle = {WWW},
  year      = {2011},
  pages     = {577-586},
  ee        = {http://doi.acm.org/10.1145/1963405.1963487},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@InProceedings{localflow-ba2011,
  title =	"Brief Announcement: Bridging the Theory-Practice Gap
		 in Multi-commodity Flow Routing",
  author =	"Siddhartha Sen and Sunghwan Ihm and Kay Ousterhout and
		 Michael J. Freedman",
  booktitle =	"International Symposium on Distributed Computing",
  year = 	"2011",
  pages =	"205--207",
}

@article{DBLP:journals/corr/abs-1112-0784,
  author    = {Michael A. Bender and Jeremy T. Fineman and Seth Gilbert and Robert Endre Tarjan},
  title     = {A New Approach to Incremental Cycle Detection and Related Problems},
  journal   = {CoRR},
  volume    = {abs/1112.0784},
  year      = {2011},
  ee        = {http://arxiv.org/abs/1112.0784},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DBLP:conf/wads/Tarjan11,
  author    = {Robert Endre Tarjan},
  title     = {Theory vs. Practice in the Design and Analysis of Algorithms},
  booktitle = {WADS},
  year      = {2011},
  pages     = {703},
  ee        = {http://dx.doi.org/10.1007/978-3-642-22300-6_60},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DBLP:conf/esa/GoldbergHKTW11,
  author    = {Andrew V. Goldberg and Sagi Hed and Haim Kaplan and Robert Endre Tarjan and Renato Fonseca F. Werneck},
  title     = {Maximum Flows by Incremental Breadth-First Search},
  booktitle = {ESA},
  year      = {2011},
  pages     = {457-468},
  ee        = {http://dx.doi.org/10.1007/978-3-642-23719-5_39},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{DBLP:journals/talg/GeorgiadisKSTW11,
  author    = {Loukas Georgiadis and Haim Kaplan and Nira Shafrir and Robert Endre Tarjan and Renato Fonseca F. Werneck},
  title     = {Data structures for mergeable trees},
  journal   = {ACM Transactions on Algorithms},
  volume    = {7},
  number    = {2},
  year      = {2011},
  pages     = {14},
  ee        = {http://doi.acm.org/10.1145/1921659.1921660},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{DBLP:journals/siamcomp/HaeuplerST11,
  author    = {Bernhard Haeupler and Siddhartha Sen and Robert Endre Tarjan},
  title     = {Rank-Pairing Heaps},
  journal   = {SIAM J. Comput.},
  volume    = {40},
  number    = {6},
  year      = {2011},
  pages     = {1463-1485},
  ee        = {http://dx.doi.org/10.1137/100785351},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{KSS11,
author = {Kahn, Jeff and Saks, Michael and Smyth, Cliff},
title = {The Dual BKR Inequality and Rudich's Conjecture},
journal = {Combinatorics, Probability and Computing},
volume = {20},
number = {02},
pages = {257-266},
year = {2011},
}

@inproceedings{LeeMRSS11,
  author    = {Troy Lee and Rajat Mittal and Ben W. Reichardt and Robert Spalek and Mario Szegedy},
  title     = {Quantum Query Complexity of State Conversion},
  booktitle = {FOCS},
  year      = {2011},
  pages     = {344-353},
  ee        = {http://dx.doi.org/10.1109/FOCS.2011.75},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{szegedy1,
 author = {K. Kolipaka and M. Szegedy.},
 title = {Moser and {T}ardos meet {L}ov\'asz},
 booktitle = {STOC},
 year = {2011},
 }

@InProceedings{accdepth,
    author = "F. Wang",
    title = "{NEXP} Does Not Have Non-Uniform Quasipolynomial-Size 
    {ACC} Circuits of $o(\log\log n)$ Depth",
  booktitle =    "8th Annual Conference on Theory and Applications 
  of Models of Computation (TAMC)",
  year =         "2011",
}

@article{simplicity,
    author = "E. Allender and H. Spakowski",
  title     = {Avoiding Simplicity is Complex},
  journal   = {Theory of Computing Systems},
  year      = {2011},
  note     = {to appear},
}

@inproceedings{icalp.k,
  author    = "E. Allender and L. Friedman and W. Gasarch",
  title     = {Limits on the Computational Power of Random Strings},
  booktitle = "ICALP (1)",
  year      = {2011},
}

@inproceedings{icalp.imm,
  author    = "E. Allender and F. Wang",
  title     = {On the Power of Algebraic Branching Programs of Width Two},
  booktitle = "ICALP",
  year      = {2011},
}

@inproceedings{DBLP:conf/www/GupteSLMI11,
  author    = {Mangesh Gupte and
               Pravin Shankar and
               Jing Li and
               S. Muthukrishnan and
               Liviu Iftode},
  title     = {Finding hierarchy in directed online social networks},
  booktitle = {WWW},
  year      = {2011},
  pages     = {557-566},
  ee        = {http://doi.acm.org/10.1145/1963405.1963484},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DBLP:conf/soda/FoxGLNP11,
  author    = {Jacob Fox and
               Mikhail Gromov and
               Vincent Lafforgue and
               Assaf Naor and
               J{\'a}nos Pach},
  title     = {Overlap properties of geometric expanders},
  booktitle = {SODA},
  year      = {2011},
  pages     = {1188-1197},
}

@inproceedings{KM11,
  author    = {Subhash Khot and Dana Moshkovitz},
  title     = {NP-hardness of approximately solving linear equations over reals},
  booktitle = {STOC},
  year      = {2011},
  pages     = {413-420},
}

@inproceedings{AK11,
  author    = {Per Austrin and Subhash Khot},
  title     = {A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem},
  booktitle = {ICALP (1)},
  year      = {2011},
  pages     = {474-485},
}

@inproceedings{KhotS11,
  author    = {Subhash Khot and Muli Safra},
  title     = {A Two Prover One Round Game with Strong Soundness},
  booktitle = {FOCS},
  year      = {2011},
  pages     = {648-657},
  ee        = {http://dx.doi.org/10.1109/FOCS.2011.62},
}

@inproceedings{CHSS11,
  author    = {Steve Chien and Prahladh Harsha and Alistair Sinclair and Srikanth Srinivasan},
  title     = {Almost settling the hardness of noncommutative determinant},
  booktitle = {STOC},
  year      = {2011},
  pages     = {499-508},
}

@inproceedings{LS11a,
  author    = {Shachar Lovett and Srikanth Srinivasan},
  title     = {Correlation Bounds for Poly-size ${A}{C}^0$ Circuits with $n^{1 - o(1)}$ Symmetric Gates},
  booktitle = {APPROX-RANDOM},
  year      = {2011},
  pages     = {640-651},
  ee        = {http://dx.doi.org/10.1007/978-3-642-22935-0_54},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{ODonnellWZ11b,
  author    = {Ryan O'Donnell and John Wright and Yuan Zhou},
  title     = {The Fourier Entropy-Influence Conjecture for Certain Classes of Boolean Functions},
  booktitle = {ICALP (1)},
  year      = {2011},
  pages     = {330-341},
  ee        = {http://dx.doi.org/10.1007/978-3-642-22006-7_28},
}

@inproceedings{ODonnellWZ11,
  author    = {Ryan O'Donnell and Yi Wu and Yuan Zhou},
  title     = {Hardness of {M}ax-2{L}in and {M}ax-3{L}in over Integers, Reals, and Large Cyclic Groups},
  booktitle = {IEEE Conference on Computational Complexity},
  year      = {2011},
  pages     = {23-33},
  ee        = {http://dx.doi.org/10.1109/CCC.2011.37},
}

@inproceedings{Imp11,
  author    = {Russell Impagliazzo},
  title     = {Relativized Separations of Worst-Case and Average-Case Complexities for NP},
  booktitle = {IEEE Conference on Computational Complexity},
  year      = {2011},
  pages     = {104-114},
  ee        = {http://dx.doi.org/10.1109/CCC.2011.34},
}

@article{HatamiLovett11:complexity,
    author = {Hamed Hatami and Shachar Lovett},
    title = {Higher-order {F}ourier analysis of ${F}_p^n$ and the complexity of systems of linear forms},
    journal = {Geometric and Functional Analysis},
    year = {2011},
    volume = {21},
    issue = {6},
    pages = {1331-1357},
}

@inproceedings{HatamiLovett11:testing,
    author = {Hamed Hatami and Shachar Lovett},
    title = {Correlation testing of Affine Invariant properties on ${F}_p^n$ in the high error regime},
    booktitle = {STOC},
    year = {2011},
}

@inproceedings{ChattopadhyayLovett11,
    author = {Arkadev Chattopadhyay and Shachar Lovett},
    title = {Linear systems over finite abelian groups},
    booktitle = {26th IEEE Conference on Computational Complexity (CCC)},
    year = {2011},
}

@inproceedings{LovettViola11,
    author = {Shachar Lovett and Emanuele Viola},
    title = {Bounded-depth circuits cannot sample good codes},
    booktitle = {The 26th IEEE Conference on Computational Complexity (CCC)},
    year = {2011},
}

@inproceedings{KSY11,
  author    = {Swastik Kopparty and Shubhangi Saraf and Sergey Yekhanin},
  title     = {High-rate codes with sublinear-time decoding},
  booktitle = {STOC},
  year      = {2011},
  pages     = {167-176},
}

@inproceedings{Kopparty11,
  author    = {Swastik Kopparty},
  title     = {On the complexity of powering in finite fields},
  booktitle = {STOC},
  year      = {2011},
  pages     = {489-498},
}

@inproceedings{DBLP:conf/focs/BravermanMMN11,
  author    = {Mark Braverman and
               Konstantin Makarychev and
               Yury Makarychev and
               Assaf Naor},
  title     = {The Grothendieck Constant is Strictly Smaller than Krivine's
               Bound},
  booktitle = {FOCS},
  year      = {2011},
  pages     = {453-462},
  ee        = {http://dx.doi.org/10.1109/FOCS.2011.77},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{BDYW11,
  author    = {Boaz Barak and Zeev Dvir and Amir Yehudayoff and Avi Wigderson},
  title     = {Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes},
  booktitle = {STOC},
  year      = {2011},
  pages     = {519-528},
}

@inproceedings{FrongilloST11,
  author = {Rafael M. Frongillo and Grant Schoenebeck and Omer Tamuz},
  title = {Social Learning in a Changing World},
  year = {2011},
  booktitle = "Workshop on Internet and Network Economics (WINE)"
}

@unpublished{RisteskiT2011,
  author = "A. Risteski and R. E. Tarjan",
  title = "Batch algorithm for level-based incremental topological sorting",
  note = "Manuscript",
  year = {2011}
}




%Tarjan

@inproceedings{GMRZ,
  author    = {Parikshit Gopalan and
               Raghu Meka and
               Omer Reingold and
               David Zuckerman},
  title     = {Pseudorandom generators for combinatorial shapes},
  booktitle = {STOC},
  year      = {2011},
  pages     = {253-262},
  ee        = {http://doi.acm.org/10.1145/1993636.1993671},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@InProceedings{BV,
  author    = {Aditya Bhaskara and
               Aravindan Vijayaraghavan},
  title     = {Approximating the Matrix p-norm},
  booktitle = {SODA},
  year = {2011},
  ee        = {http://arxiv.org/abs/1001.2613},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}



%Ankur

@unpublished{MN11-haus,
    author={Mendel, M. and Naor, A.},
    title = {Ultrametric subsets with large Hausdorff dimension},
    note={To appear in Inventiones mathematicae. http://arxiv.org/abs/1106.0879},
    year = {2011},
}

@unpublished{MN11-skel,
    author={Mendel, M. and Naor, A.},
    title = {Ultrametric skeletons},
    note={To appear in Proceedings of the National Academy of Sciences. http://arxiv.org/abs/1112.3416},
    year = {2011},
}

@inproceedings{SS11,
  author = {Sachdeva, Sushant and Saket, Rishi},
  booktitle = {APPROX-RANDOM},
  pages = {327-338},
  publisher = {Springer},
  series = {Lecture Notes in Computer Science},
  title = {Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs},
  url = {http://dblp.uni-trier.de/db/conf/approx/approx2011.html#SachdevaS11},
  volume = 6845,
  year = 2011
}

@unpublished{SachdevaT11,
  author =	 {Sushant Sachdeva and Madhur Tulsiani},
  title =	 {Cuts in {C}artesian Products of Graphs},
  note =	 {Manuscript.  arXiv:1105.3383},
  year =	 2011,
}

@article{Alekhnovich_Borodin_Buresh-Oppenheim_Impagliazzo_Magen_Pitassi_2005,
title={Toward a Model for Backtracking and Dynamic Programming},
journal={Computational Complexity},
author={Alekhnovich, Michael and Borodin, Allan and Buresh-Oppenheim, Joshua and Impagliazzo, Russell and Magen, Avner and Pitassi, Toniann},
year={2011},
volume={20},
number={4},
pages={679--740}}

@article {springerlink:10.1007/s00453-009-9385-1,
   author = {Buresh-Oppenheim, Joshua and Davis, Sashka and Impagliazzo, Russell},
   affiliation = {Akamai Technologies, Cambridge, USA},
   title = {A Stronger Model of Dynamic Programming Algorithms},
   journal = {Algorithmica},
   publisher = {Springer New York},
   issn = {0178-4617},
   keyword = {Computer Science},
   pages = {938-968},
   volume = {60},
   issue = {4},
   url = {http://dx.doi.org/10.1007/s00453-009-9385-1},
   note = {10.1007/s00453-009-9385-1},
   year = {2011}
}

@inproceedings{DHK+:10,
  author    = {Ilias Diakonikolas and
               Prahladh Harsha and
               Adam Klivans and
               Raghu Meka and
               Prasad Raghavendra and
               Rocco A. Servedio and
               Li-Yang Tan},
  title     = {Bounding the average sensitivity and noise sensitivity of
               polynomial threshold functions},
  booktitle = {STOC},
  year      = {2010},
  pages     = {533-542},
}

@inproceedings{GS:10random,
  author={P. Gopalan and R. Servedio},
  title={{Learning and lower bounds for $AC^0$ with threshold gates}},
  booktitle = {RANDOM},
  year      = {2010},
  pages     = {588-601}
}

@inproceedings{LS:10icml,
  author    = {P. Long and R. Servedio},
  title     = {Restricted Boltzmann Machines are Hard to Approximately
Evaluate or Simulate},
  booktitle = {ICML},
  year      = {2010},
  pages     = {703-710}
}

@article{DLMW10:algorithmica,
  author={I. Diakonikolas and H.K. Lee and K. Matulef and R. Servedio and
A. Wan},
  title={Efficiently Testing Sparse $GF(2)$ Polynomials},
  journal={Algorithmica},
  year={2010}
}

@article{DGJ+10:bifh,
  author={I. Diakoniokolas and P. Gopalan and
  R. Jaiswal and R. Servedio and E. Viola},
  title={Bounded Independence Fools Halfspaces},
  journal={SIAM Journal on Computing},
  volume={39},
  number={8},
  pages={3441-3462},
  year={2010}
}

@article{OS10:combinatorica,
  author={R. O'Donnell and R. Servedio},
  title={{New Degree Bounds for Polynomial Threshold Functions}},
  journal={Combinatorica},
  volume={30},
  number={3},
  pages={327-358},
  year={2010}
}

@inproceedings{DSTW:10,
  author={I. Diakonikolas and R. Servedio and L.-Y. Tan and A. Wan},
  title={A regularity lemma, and low-weight approximators, for low-degree
  polynomial threshold functions},
  booktitle = {{CCC}},
  year={2010},
  pages={211-222}
}

@inproceedings{ABNS10,
 author = {Abraham, Ittai and Bartal, Yair and Neiman, Ofer and Schulman, Leonard J.},
 title = {Volume in general metric spaces},
 booktitle = {18th ESA},
 year = {2010},
 pages = {87--99},
}

@inproceedings{DBLP:conf/focs/HardtR10,
  author    = {Moritz Hardt and
               Guy N. Rothblum},
  title     = {A Multiplicative Weights Mechanism for Privacy-Preserving
               Data Analysis},
  booktitle = {FOCS},
  year      = {2010},
  pages     = {61-70},
  ee        = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2010.85},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DBLP:conf/crypto/DeTT10,
  author    = {Anindya De and
               Luca Trevisan and
               Madhur Tulsiani},
  title     = {Time Space Tradeoffs for Attacks against One-Way Functions
               and PRGs},
  booktitle = {CRYPTO},
  year      = {2010},
  pages     = {649-665},
  ee        = {http://dx.doi.org/10.1007/978-3-642-14623-7_35},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DBLP:conf/approx/DeETT10,
  author    = {Anindya De and
               Omid Etesami and
               Luca Trevisan and
               Madhur Tulsiani},
  title     = {Improved Pseudorandom Generators for Depth 2 Circuits},
  booktitle = {APPROX-RANDOM},
  year      = {2010},
  pages     = {504-517},
  ee        = {http://dx.doi.org/10.1007/978-3-642-15369-3_38},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DBLP:conf/approx/BateniHZ10,
  author    = {MohammadHossein Bateni and
               MohammadTaghi Hajiaghayi and
               Morteza Zadimoghaddam},
  title     = {Submodular Secretary Problem and Extensions},
  booktitle = {APPROX},
  year      = {2010},
  pages     = {39-52},
  ee        = {http://dx.doi.org/10.1007/978-3-642-15369-3_4},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{GKRS10,
author = {Anupam Gupta and Aaron Roth and  Grant Schoenebeck and Kunal Talwar},
title = {Constrained Non-monotone Submodular Maximization: Offline and Secretary Algorithms},
 booktitle = {The 6th Workshop on Internet and Network Economics (WINE 2010)},
 month = "December",
 year = {2010}
}

@inproceedings{BKSSZ10,
author = {Arnab Bhattacharyya and Swastik Kopparty and Grant Schoenebeck and Madhu Sudan and David Zuckerman},
title = {Optimal Testing of Reed-Muller Codes},
booktitle = {FOCS},
year = {2010},
}

@inproceedings{AC10,
  AUTHOR = {N. Ailon and B. Chazelle},
   TITLE = {Faster Dimension Reduction},
 booktitle = "Communications of the ACM",
    YEAR = {2010},
    }

@inproceedings{CC10,
  AUTHOR = {S. Comandur and B. Chazelle},
   TITLE = {Online Geometric Reconstruction},
 booktitle = "Journal of the ACM",
    YEAR = {2010},
    }

@inproceedings{C10-1,
  AUTHOR = {B. Chazelle},
   TITLE = {A Geometric Approach to Collective Motion},
 booktitle = "Proc. 26th ACM SoCG",
    YEAR = {2010},
    }

@inproceedings{C10-2,
  AUTHOR = {B. Chazelle},
   TITLE = {The Geometry of Flocking},
 booktitle = "Proc. 26th ACM SoCG",
    YEAR = {2010},
    }

@inproceedings{SaksSesh-approxlis10,
  author    = {Saks, Michael and
               Seshadhri, C.},
  title     = {Estimating the Longest Increasing Sequence in Polylogarithmic
               Time},
  booktitle = {FOCS},
  year      = {2010},
  pages     = {458-467},
  ee        = {http://dx.doi.org/10.1109/FOCS.2010.51},
  bibsource = {DBLP, http://dblp.uni-trier.de},
}

@article{DBLP:GoyalSaks10,
  author    = {Navin Goyal and
               Michael Saks},
  title     = {Rounds vs. Queries Tradeoff in Noisy Computation},
  journal   = {Theory of Computing},
  volume    = {6},
  number    = {1},
  year      = {2010},
  pages     = {113-134},
  ee        = {http://dx.doi.org/10.4086/toc.2010.v006a006},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{LS10,
  author    = {Nikos Leonardos and
               Michael Saks},
  title     = {Lower Bounds on the Randomized Communication Complexity
               of Read-Once Functions},
  journal   = {Computational Complexity},
  volume    = {19},
  number    = {2},
  year      = {2010},
  pages     = {153-181},
  ee        = {http://springerlink.metapress.com/content/y42hkrn487280635/},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{pervasive,
  author =    "E.~Allender and M.~Kouck\'y and D.~Ronneburger and S.~Roy",
  title     = {The pervasive reach of resource-bounded {Kolmogorov} complexity in computational complexity theory},
  journal =  "Journal of Computer and System Sciences",
volume = {77},
pages = {14--40},
year = {2010}
}

@InCollection{questions,
  author =       {E.~Allender},
  title =        {Randomness as Circuit Complexity (and the Connection to Pseudorandomness)},
  booktitle =    {Randomness through Computation: Some answers, more questions},
  publisher =    {World Scientific Press},
  year =         2010,
  editor =       {Hector Zenil},
  pages =        "267 -- 274",
}

@InProceedings{symauxpda,
  author =       "E. Allender and K.-J. Lange",
  title =        "Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata",
  booktitle =    "IEEE Conference on Computational Complexity (CCC)",
  year =         "2010",
  pages =        "172 -- 180",
}

@InProceedings{cie,
  author =       "E. Allender",
  title =        "Avoiding Simplicity is Complex",
  booktitle =    "Programs, Proofs, Processes: 6th Conference of
Computability in Europe, (CiE)",
  Series =      "Lecture Notes in Computer Science",
  volume =       "6158",
  year =         "2010",
  pages =        "1 -- 10",
}

@InProceedings{cie.surv,
  author =       "E. Allender",
  title =        "New Surprises from Self-Reducibility",
  booktitle =    "Programs, Proofs, Processes: 6th Conference of
Computability in Europe, (CiE), Abstract and Handout Booklet",
  note = "Invited Plenary Talk",
  year =         "2010",
  pages =        "1 -- 5",
}

@inproceedings{DBLP:conf/icalp/GuruswamiKOPTW10,
  author    = {Venkatesan Guruswami and
               Subhash Khot and
               Ryan O'Donnell and
               Preyas Popat and
               Madhur Tulsiani and
               Yi Wu},
  title     = {{SDP} Gaps for 2-to-1 and Other Label-Cover Variants},
  booktitle = {ICALP (1)},
  year      = {2010},
  pages     = {617-628},
  ee        = {http://dx.doi.org/10.1007/978-3-642-14165-2_52},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DBLP:conf/pods/GupteS10,
  author    = {Mangesh Gupte and
               Mukund Sundararajan},
  title     = {Universally optimal privacy mechanisms for minimax agents},
  booktitle = {ACM symposium on Principles of Database Systems (PODS)},
  year      = {2010},
  pages     = {135-146},
  ee        = {http://doi.acm.org/10.1145/1807085.1807105},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{CT10bbb,
  author    = {Eden Chlamtach and Madhur Tulsiani},
  year = {2010},
  booktitle = {Handbook on Semidefinite, Cone and Polynomial Optimization},
  title = {Convex Relaxations and Integrality Gaps},
}

@inproceedings{ImpWil10,
  author    = {Russell Impagliazzo and Ryan Williams},
  title     = {Communication Complexity with Synchronized Clocks},
  booktitle = {IEEE Conference on Computational Complexity},
  year      = {2010},
  pages     = {259-269},
  ee        = {http://doi.ieeecomputersociety.org/10.1109/CCC.2010.32},
}

@inproceedings{IK10,
  author    = {Russell Impagliazzo and
               Valentine Kabanets},
  title     = {Constructive Proofs of Concentration Bounds},
  booktitle = {APPROX-RANDOM},
  year      = {2010},
  pages     = {617-631},
  ee        = {http://dx.doi.org/10.1007/978-3-642-15369-3_46},
}

@article{BI10,
  author    = {Eli Ben-Sasson and Russell Impagliazzo},
  title     = {Random Cnf's are Hard for the Polynomial Calculus},
  journal   = {Computational Complexity},
  volume    = {19},
  number    = {4},
  year      = {2010},
  pages     = {501-519},
}

@inproceedings{CIP10,
  author    = {Chris Calabro and Russell Impagliazzo and Ramamohan Paturi},
  title     = {On the Exact Complexity of Evaluating Quantified {\it }-CNF},
  booktitle = {IPEC},
  year      = {2010},
  pages     = {50-59},
}

@inproceedings{HWY,
  author    = {Pavel Hrubes and Avi Wigderson and Amir Yehudayoff},
  title     = {Non-commutative circuits and the sum-of-squares problem},
  booktitle = {STOC},
  year      = {2010},
  pages     = {667-676},
}

@inproceedings{DBLP:conf/stoc/BhaskaraCCFV10,
  author    = {Aditya Bhaskara and
               Moses Charikar and
               Eden Chlamtac and
               Uriel Feige and
               Aravindan Vijayaraghavan},
  title     = {Detecting high log-densities: an {\it O}({\it n}$^{\mbox{1/4}}$)
               approximation for densest {\it k}-subgraph},
  booktitle = {STOC},
  year      = {2010},
  pages     = {201-210},
  ee        = {http://doi.acm.org/10.1145/1806689.1806718},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DBLP:conf/focs/CharikarLLM10,
  author    = {Moses Charikar and
               Tom Leighton and
               Shi Li and
               Ankur Moitra},
  title     = {Vertex Sparsifiers and Abstract Rounding Algorithms},
  booktitle = {FOCS},
  year      = {2010},
  pages     = {265-274},
  ee        = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2010.32},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{HWYrel,
  author    = {Pavel Hrubes and Avi Wigderson and Amir Yehudayoff},
  title     = {Relationless Completeness and Separations},
  booktitle = {IEEE Conference on Computational Complexity},
  year      = {2010},
  pages     = {280-290},
  ee        = {http://doi.ieeecomputersociety.org/10.1109/CCC.2010.34},
}




%%%ABOVE IS NEW ADDITIONS





%zeev

@unpublished{ANTbbb,
author = {T. Austin and A. Naor and R. Tessera},
title = {Sharp quantitative nonembeddability of the Heisenberg group into superreflexive Banach spaces},
year = {2010},
note = {To appear in Groups, Geometry and Dynamics.  arXiv:1007.4238},
}

@inproceedings{DBLP:conf/infocom/BateniGHS09,
  author    = {MohammadHossein Bateni and
               Alexandre Gerber and
               Mohammad Taghi Hajiaghayi and
               Subhabrata Sen},
  title     = {Multi-VPN Optimization for Scalable Routing via Relaying},
  booktitle = {INFOCOM},
  year      = {2009},
  pages     = {2756-2760},
  ee        = {http://dx.doi.org/10.1109/INFCOM.2009.5062226},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DBLP:conf/stoc/KunS09,
  author    = {G{\'a}bor Kun and
               Mario Szegedy},
  title     = {A new line of attack on the dichotomy conjecture},
  booktitle = {STOC},
  year      = {2009},
  pages     = {725-734},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{CIP09,
  author    = {Chris Calabro and Russell Impagliazzo and Ramamohan Paturi},
  title     = {The Complexity of Satisfiability of Small Depth Circuits},
  booktitle = {IWPEC},
  year      = {2009},
  pages     = {75-85},
  ee        = {http://dx.doi.org/10.1007/978-3-642-11269-0_6},
}