1. Ittai Abraham and Yair Bartal and Ofer Neiman and Leonard J. Schulman, *Volume in general metric spaces*, in *Proceedings of the 18th annual European conference on Algorithms: Part II*. 2010, Springer-Verlag: Liverpool, UK. p. 87-99.

2. Nir Ailon, Bernard Chazelle, Ding Liu, Comandur Seshadhri, *Self-Improving Algorithms*, in *SIAM Journal on Computing*. 2011.

3. Nir Ailon, Bernard Chazelle, *Faster Dimension Reduction*, in *Communications of the ACM*. 2010.

4. E. Allender, *New Surprises from Self-Reducibility*, in *Programs, Proofs, Processes: 6th Conference of Computability in Europe, (CiE), Abstract and Handout Booklet*. 2010. p. 1 - 5.

5. E. Allender, *Randomness as Circuit Complexity (and the Connection to Pseudorandomness)*, in *Randomness through Computation: Some answers, more questions*. 2010, World Scientific Press. p. 267 - 274.

6. E. Allender and L. Friedman and W. Gasarch, *Limits on the Computational Power of Random Strings*, in *Proc. of International Conference on Automata, Languages, and Programming (ICALP)*. 2011.

7. E. Allender and F. Wang, *On the Power of Algebraic Branching Programs of Width Two*, in *Proc. of International Conference on Automata, Languages, and Programming (ICALP)*. 2011.

8. Noga Alon and Sanjeev Arora and Rajsekar Manokaran and Dana Moshkovitz and Omri Weinstein, *On the Inapproximability of the Densest $k$-Subgraph problem*, in *manuscript*. 2011: manuscript.

9. Noga Alon and Shachar Lovett, *Weighted families of $k$-wise independent permutations*, in *manuscript*. 2011.

10. G. Kun and M. Szegedy, *A new line of attack on the dichotomy conjecture.* Theory of Computing, submitted, 2011.

11. A. Andoni and A. Naor and O. Neiman, *On isomorphic dimenion reduction in $\ell_1$.*

12. Aaron Archer and MohammadHossein Bateni and MohammadTaghi Hajiaghayi and Howard J. Karloff, *Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP.* SIAM J. Comput., 2011. **40**(2): p. 309-332.

13. Sanjeev Arora and Boaz Barak and Markus Brunnermeier and Rong Ge, *Computational Complexity and Information Asymmetry in Financial Products.* Communications of the ACM, 2011. **54**(5): p. 101-107.

14. Sanjeev Arora and Aditya Bhaskara, *Properties of Eigenvectors of Random Graphs.* Submitted, 2011.

15. Sanjeev Arora and Rong Ge, *New Algorithms for Learning in Presence of Errors.* to appear in ICALP 2011, 2011.

16. Sanjeev Arora and Rong Ge, *New Tools for Graph Coloring.* Submitted, 2011.

17. Sanjeev Arora and James R. Lee and Sushant Sachdeva, *A Reformulation of the Arora-Rao-Vazirani Structure Theorem.* CoRR, 2011. **abs/1102.1456**.

18. T. Austin and A. Naor and R. Tessera, *Sharp quantitative nonembeddability of the Heisenberg group into superreflexive Banach spaces.*

19. Per Austrin and Subhash Khot, *A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem*, in *ICALP*. 2011.

20. B. Barak and Z. Dvir and A. Wigderson and A. Yehudayoff, *Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes*, in *STOC 2011*. 2011: STOC 2011.

21. Mohammad Hossein Bateni and Chandra Chekuri and Alina Ene and MohammadTaghi Hajiaghayi and Nitish Korula and Dániel Marx, *Prize-collecting Steiner Problems on Planar Graphs*, in *SODA*. 2011.

22. Mohammad Hossein Bateni and Julia Chuzhoy, *Approximation Algorithms for the Directed $k$-Tour and $k$-Stroll Problems*, in *APPROX*. 2010. p. 25-38.

23. Mohammad Hossein Bateni and Alexandre Gerber and Mohammad Taghi Hajiaghayi and Subhabrata Sen, *Multi-VPN Optimization for Scalable Routing via Relaying.* IEEE/ACM Trans. Netw., 2010. **18**(5): p. 1544-1556.

24. Mohammad Hossein Bateni and MohammadTaghi Hajiaghayi and Dániel Marx, *Prize-collecting Network Design on Planar Graphs.* CoRR, 2010. **abs/1006.4339**.

25. Mohammad Hossein Bateni and MohammadTaghi Hajiaghayi and Morteza Zadimoghaddam, *Submodular Secretary Problem and Extensions*, in *APPROX*. 2010. p. 39-52.

26. Mohammad Hossein Bateni and Mohammad Taghi Hajiaghayi and Sina Jafarpour and Dan Pei, *Towards an efficient algorithmic framework for pricing cellular data service*, in *INFOCOM*. 2011.

27. Paul Beame and Russell Impagliazzo and Srikanth Srinivasan, *Approximating $\mathrmAC^0$ circuits by Small Height Decision Trees*, in *Submitted*. 2011.

28. Aditya Bhaskara and Moses Charikar and Eden Chlamtac and Uriel Feige and Aravindan Vijayaraghavan, *Detecting High Log-Densities - an O(n^1/4) Approximation for Densest k-Subgraph*, in *Proc1 $42$nd Symposium on Theory of Computing (STOC)*. 2010, ACM.

29. Aditya Bhaskara and Moses Charikar and Rajsekar Manokaran and Aravindan Vijayaraghavan, *On Quadratic Programming with a Ratio Objective.* Submitted, 2010.

30. Aditya Bhaskara and Moses Charikar and Aravindan Vijayaraghavan, *Tight integrality gaps for strong relaxations of the densest $k$-subgraph problem.* Submitted., 2011.

31. Aditya Bhaskara and Ravi Kannan, *Moment based Concentration Inequalities for Geometric Problems.* In Preparation, 2011.

32. Aditya Bhaskara and Aravindan Vijayaraghavan, *Approximating the Matrix p-norm*, in *Proc1 $22$nd Symposium on Discrete Algorithms (SODA)*. 2011, ACM-SIAM.

33. A. Bhattacharyya and Z. Dvir and S. Saraf and A. Shpilka, *Tight lower bounds for 2-query LCCs over finite fields*, in manuscript

34. Enrico Bombieri and Swastik Kopparty, *List-decoding Multiplicity Codes*, in *in preparation*. 2011.

35. Mark Braverman and Konstantin Makarychev and Yury Makarychev and Assaf Naor, *The Grothendieck constant is strictly smaller than Krivine's bound. FOCS 2011.*

36. Chris Calabro and Russell Impagliazzo and Ramamohan Paturi, *On the Exact Complexity of Evaluating Quantified \it -CNF*, in *IPEC*. 2010. p. 50-59.

37. Moses Charikar and Tom Leighton and Shi Li and Ankur Moitra, *Vertex Sparsifiers and Abstract Rounding Algorithms*, in *Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science*. 2010. p. 265-274.

38. Moses Charikar and Shi Li, *A Dependent LP-rounding Approach for the $k$-Median Problem*, in manuscript

39. Moses Charikar and Alantha Newman and Aleksandar Nikolov, *Tight Hardness Results for Minimizing Discrepancy*, in *Proc1 $22$nd Symposium on Discrete Algorithms (SODA)*. 2011, ACM-SIAM. p. 1607-1614.

40. Arkadev Chattopadhyay and Shachar Lovett, *Linear systems over finite abelian groups*, in *The 26th IEEE Conference on Computational Complexity (CCC)*. 2011.

41. B. Chazelle, *Spreading Influence in a Changing World*, in *Manuscript*. 2011.

42. Steve Chien and Prahladh Harsha and Alistair Sinclair and Srikanth Srinivasan, *Almost Settling the Hardness of the Noncommutative Determinant*, in *To appear in STOC 2011*. 2011.

43. Eden Chlamtac and Madhur Tulsiani, *Convex Relaxations and Integrality Gaps.* Handbook on Semidefinite, Cone and Polynomial Optimization, 2010.

44. Julia Chuzhoy and Yury Makarychev and Aravindan Vijayaraghavan and Yuan Zhou, *On approximating $k$-route cuts.* Manuscript., 2011.

45. Chazelle B. Comandur S., *Online Geometric Reconstruction*, in *Journal of the ACM*. 2010.

46. D. Dachman-Soled and R. Servedio, *A canonical form for testing Boolean function properties*, in manuscript

47. C. Daskalakis and I. Diakonikolas and R. Servedio, *Learning and testing $k$-modal distributions*, in manuscript

48. C. Daskalakis and I. Diakonikolas and R. Servedio, *Learning Poisson Binomial Distributions*, in manuscript

49. Anindya De and Omid Etesami and Luca Trevisan and Madhur Tulsiani, *Improved Pseudorandom Generators for Depth 2 Circuits*, in *RANDOM*. 2010.

50. Anindya De and Luca Trevisan and Madhur Tulsiani, *Time-Space Tradeoffs for Attacks against One-Way Functions and PRGs*, in *CRYPTO*. 2010.

51. Ilias Diakonikolas and Prahladh Harsha and Adam Klivans and Raghu Meka and Prasad Raghavendra and Rocco A. Servedio and Li-Yang Tan, *Bounding the average sensitivity and noise sensitivity of polynomial threshold functions*, in *STOC*. 2010. p. 533-542.

52. I. Diakonikolas and H.K. Lee and K. Matulef and R. Servedio and A. Wan, *Efficiently Testing Sparse $GF(2)$ Polynomials.* Algorithmica, 2010.

53. I. Diakonikolas and R. O'Donnell and R. Servedio and Y. Wu, *Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions*, in *SODA*. 2011. p. 1590-1606.

54. I. Diakonikolas and R. Servedio and L.-Y. Tan and A. Wan, *A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions*, in *CCC*. 2010. p. 211-222.

55. I. Diakoniokolas and P. Gopalan and R. Jaiswal and R. Servedio and E. Viola, *Bounded Independence Fools Halfspaces.* SIAM Journal on Computing, 2010. **39**(8): p. 3441-3462.

56. Wei Dong and Moses Charikar and Kai Li, *Efficient k-nearest neighbor graph construction for generic similarity measures*, in *WWW*. 2011. p. 577-586.

57. Z. Dvir and D. Gutfreund and G. Rothblum and S. Vadhan, *On approximating the entropy of polynomial mappings*, in *Proceedings of the Second Symposium on Innovations in Computer Science (ICS 2011), Beijing, China, 7-9 January 2011*. 2011.

58. Cynthia Dwork and Moritz Hardt and Toniann Pitassi and Omer Reingold and Richard Zemel, *Fairness through awareness.* CoRR, 2011. **abs/1104.3913**.

59. V. Feldman and H. Lee and R. Servedio, *Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas*, in *COLT*. 2011. p. to appear.

60. O. Giladi and A. Naor, *Bourgain's discretization theorem.*

61. A. Goldberg and S. Hed and H. Kaplan and R. Tarjan and R. Werneck, *Maximum flows by incremental breadth-first search*, in *European Symposium on Algorithms*. 2011.

62. P. Gopalan and R. Servedio, *Learning and lower bounds for $AC^0$ with threshold gates*, in *RANDOM*. 2010. p. 588-601.

63. Anupam Gupta and Moritz Hardt and Aaron Roth and Jon Ullman, *Privately Releasing Conjunctions and the Statistical Query Barrier*, in *Proc1 $43$nd STOC*. 2011, ACM.

64. Anupam Gupta and Aaron Roth and Grant Schoenebeck and Kunal Talwar, *Constrained Non-monotone Submodular Maximization: Offline and Secretary Algoritms*, in *The 6th Workshop on Internet and Network Economics (WINE 2010)*. 2010.

65. M. Gupte and D. Krushevskaja and S. Muthukrishnan, *Cardinal Auctions: Revenue and Efficiency Analysis*.

66. Mangesh Gupte and Mukund Sundararajan, *Universally Optimal Privacy Mechanisms for Minimax Agents*, in *PODS'10: Proceedings of the 29th annual ACM symposium on Principles of Database Systems*. 2010, ACM: Indianapolis, Indiana, USA.

67. M. and Shakar Gupte, P. and Li, J. Muthukrishnan, S. and and L. Iftode, *Finding hierarchy in directed online social networks*, in *Proceedings of the 20th international conference on World Wide Web *2011, ACM: New York. p. 557-566.

68. Venkatesan Guruswami and Johan H\aastad and Rajsekar Manokaran and Prasad Raghavendra and Moses Charikar, *Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant.* Electronic Colloquium on Computational Complexity (ECCC), 2011. **18**: p. 27.

69. Venkatesan Guruswami and Subhash Khot and Preyas Popat and Ryan O'Donnell and Madhur Tulsiani and Yi Wu, *SDP Gaps for 2-to-1 and other Label Cover Variants*, in *ICALP*. 2010.

70. Bernhard Haeupler and Telikepalli Kavitha and Rogers Mathew and Siddhartha Sen and Robert Endre Tarjan, *Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance.* ACM Trans. Alg., 2011.

71. Bernhard Haeupler and Siddhartha Sen and Robert Endre Tarjan, *Rank-Pairing Heaps.* SIAM J. Comput., 2011.

72. Moritz Hardt and Katrina Ligett and Frank McSherry, *A simple and practical algorithm for differentially-private data release.* CoRR, 2010. **abs/1012.4763**.

73. Moritz Hardt and Guy Rothblum, *A Multiplicative Weights Mechanism for Privacy-Preserving Data Analysis*, in *Proc1 $51$st Foundations of Computer Science (FOCS)*. 2010, IEEE.

74. Hamed Hatami and Shachar Lovett, *Correlation testing of Affine Invariant properties on $\mathbbF_p^n$ in the high error regime*, in *The 43rd ACM Symposium on Theory of Computing (STOC)*. 2011.

75. Hamed Hatami and Shachar Lovett, *Higher-order Fourier analysis of $\mathbbF_p^n$ and the complexity of systems of linear forms.* Geometric and Functional Analysis, 2011.

76. S. Heilman and A. Jagannath and A. Naor, *Solution of the propeller conjecture in $\mathbbR^3$.*

77. Thomas Hollenstein and Grant Schoenebeck, *General Hardness Amplification of Predicates and Puzzles*, in *Theory of Cryptography Conference*. 2011.

78. J. Jackson and H.K. Lee and R. Servedio and A. Wan, *Learning Random Monotone DNF.* Discrete Applied Mathematics, 2011. **159**(5): p. 259-271.

79. Alexander Jaffe and Thomas Moscibroda and Siddhartha Sen, *The Price of Equivocation: Characterizing Byzantine Agreement via Hypergraph Coloring*, in *IEEE Symposium on Foundations of Computer Science*. 2011.

80. Jeff Kahn and Michael Saks and Cliff Smyth, *The Dual BKR Inequality and Rudich's Conjecture.* Combinatorics, Probability and Computing, 2011. **20**(02): p. 257-266.

81. S. Khot and D. Moshkovitz, *NP-Hardness of Approximately Solving Linear Equations Over Reals*, in *STOC*. 2011.

82. S. Khot and S. Safra, *A Two Prover One Round Game with Strong Soundness*, in *Submitted to FOCS*. 2011.

83. K. Kolipaka and M. Szegedy., *Moser and Tardos meet Lov\'asz*, in *STOC '11: Proceedings of the 41st annual ACM symposium on Theory of computing*. 2011, ACM: San Jose, CA, USA.

84. Swastik Kopparty, *On the complexity of powering in finite fields*, in *To appear in STOC 2011*. 2011.

85. Swastik Kopparty and Shubhangi Saraf and Sergey Yekhanin, *High-rate codes with sublinear-time decoding*, in *To appear in STOC 2011*. 2011.

86. Amit Kumar and Rajsekar Manokaran and Madhur Tulsiani and Nisheeth Vishnoi, *On the Optimality of a Class of LP-based Algorithms*, in *SODA*. 2011, SIAM.

87. G\'abor Kun and Ryan O'Donnell and Yuan Zhou, *Linear programming robustly decides width-1 CSPs*, in *manuscript*. 2011.

88. N. Leonardos and T. Lee and Michael Saks and Fengming Wang, *Informational complexity of AND in the multiparty-NOF model*

89. Shi Li, *A 1.488-approximation algorithm for the uncapacitated facility location problem*, in *Proceedings of the 38th International Colloquium on Automata, Languages and Programming*. 2011.

90. Shi Li, *A near linear time constant approximation for the earth mover distance over doubling metrics*, in *manuscript*

*91. S. Li and A. Naor, **Discretization and affine approximation ih high dimensions.*

*92. P. Long and R. Servedio, **Restricted Boltzmann Machines are Hard to Approximately Evaluate or Simulate*, in *ICML*. 2010. p. 703-710.

*93. P. Long and R. Servedio, **Learning large-margin halfspaces with more malicious noise*, in *manuscript*

*94. P. Long and R. Servedio, **On the weight of halfspaces over Hamming balls*, in *manuscript*

*95. Shachar Lovett and Srikanth Srinivasan, **Correlation bounds for poly-size $\mathrmAC^0$ circuits with $n^1-o(1)$ symmetric gates.* Submitted, 2011.

*96. Shachar Lovett and Emanuele Viola, **Bounded-depth circuits cannot sample good codes*, in *The 26th IEEE Conference on Computational Complexity (CCC)*. 2011.

*97. M. Mendel and A. Naor,** Markov convexity and local rigidity of distorted metrics.*

*98. M. Mendel and A. Naor,** A note on dichotomies for metric transforms.*

*99. M. Mendel and A. Naor, **Ultrametric subsets with large Hausdorff dimension.*

*100. Mohammad Moharrami and Sushant Sachdeva, **Power of weak v/s strong triangle inequalities.* Submitted to APPROX-RANDOM, 2011.

*101. Ankur Moitra and Ryan O'Donnell, **Pareto optimal solutions for smoothed analysts*, in *Symposium on Theory of Computation*. 2011.

*102. A. Naor, **Sparse quadrtic forms and their geometric applications.*

*103. A. Naor and O. Neiman, **Assouad's theorem with dimension independent of the snowflaking.*

*104. A. Naor and L. Silberman, **Poincar\'e inequalities, embeddings, and wild groups.*

*105. Ryan O'Donnell and G. Kun andY. Zhou, **Linear Programming robustly decides width-1 CSPs.* manuscript, 2011.

*106. R. O'Donnell and R. Servedio, **New Degree Bounds for Polynomial Threshold Functions.* Combinatorica, 2010. **30**(3): p. 327-358.

*107. R. O'Donnell and R. Servedio, **The Chow Parameters Problem.* SIAM Journal on Computing, 2011. **40**(1): p. 165-199.

*108. Ryan O'Donnell and Karl Wimmer, **Sharpness of KKL on Schreier graphs*, in manuscript

*109. Ryan O'Donnell and John Wright and Yuan Zhou, **The Fourier Entropy-Influence Conjecture for certain classes of Boolean functions*, in *International Colloquium on Automata, Languages and Programming*. 2011.

*110. Ryan O'Donnell and Yi Wu and Yuan Zhou, **Hardness of Max-2Lin and Max-3Lin over integers, reals, and large cyclic groups*, in *Conference on Computational Complexity*. 2011.

*111. A. Risteski and R. Tarjan, **Batch algorithm for level-based incremental topological sorting*, in *European Symposium on Algorithms*. 2011.

*112. Sushant Sachdeva and Rishi Saket, **Nearly Optimal NP-Hardness of Vertex Cover on $k$-Uniform $k$-Partite Hypergraphs.* Submitted to APPROX-RANDOM, 2011.

*113. Sushant Sachdeva and Madhur Tulsiani, **Cuts in Cartesian Products of Graphs.* Submitted to APPROX-RANDOM, 2011.

*114. Michael Saks and C. Seshadhri, **Space efficient streaming algorithms for path problems*

*115. Siddhartha Sen and Sunghwan Ihm and Kay Ousterhout and Michael J. Freedman, **Simple, Local Multi-commodity Flow Routing in Data Centers*, in *International Symposium on DIStributed Computing*. 2011.

*116. Siddhartha Sen and Jacob R. Lorch and Richard Hughes and Carlos G. J. Suarez and Jitendra Padhye, **NightGuard: Assuring High Availability Even As Machines Sleep*, in *ACM Symposium on Operating Systems Principles*. 2011.

*117. Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek, Mario Szegedy: Quantum Query Complexity of State Conversion. FOCS 2011.*

*118. Madhur Tulsiani, **Lovász-Schrijver Reformulation.* Encyclopedia of Operations Research and Management Science \em (Invited), 2010.

*119. Madhur Tulsiani and Julia Wolf, **Quadratic Goldreich-Levin Theorems. FOCS 2011.*

*120. F. Wang, **NEXP Does Not Have Non-Uniform Quasipolynomial-Size ACC Circuits of $o(\log\log n)$ Depth.* In *8th Annual Conference on Theory and Applications of Models of Computation (TAMC)*. 2011.

*121. Anup Rao Zeev Dvir, Avi Wigderson, and Amir Yehudayoff. **Restriction Access.* In Innovations in Theoretical Computer Science (ITCS), 2012.