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.