Publications                                                 

 All papers based on research supported fully or partly by this project.

2002-03 

  1. Fitting algebraic curves to noisy data. S. Arora, S. Khot: Journal of Computer and System Sciences, Volume 67, Issue 2, September 2003, Pages 325-340
    (prelim version in ACM STOC 2002: 162-169) postscript
  2. Similarity estimation techniques from rounding algorithms. M. Charikar: STOC 2002: 380-388
  3. Universally composable two-party and multi-party secure computation. R. Canetti, Y. Lindell, R. Ostrovsky, A. Sahai: STOC 2002: 494-503
  4. Approximating the smallest grammar: Kolmogorov complexity in natural models. M. Charikar, E. Lehman, D. Liu, R. Panigrahy, M. Prabhakaran, A. Rasala, A. Sahai, A. Shelat: STOC 2002: 792-801
  5. New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching, and Related Problems. M. Charikar, P. Indyk, R. Panigrahy: ICALP 2002: 451-462
  6. Finding Frequent Items in Data Streams. M. Charikar, K. Chen, M. Farach-Colton: ICALP 2002: 693-703, journal version in Theor. Comput. Sci. 312(1): 3-15 (2004) (special issue for ICALP 2002).
  7. Proving Integrality Gaps without Knowing the Linear Program. S. Arora, B. Bollobás, L. Lovász: FOCS 2002: 313-322. postscript
  8. Concurrent Zero Knowledge with Logarithmic Round-Complexity. M. Prabhakaran, A. Rosen, A. Sahai: FOCS 2002: 366-375
  9. Dimension Reduction in the l1 Norm. M. Charikar, A. Sahai: FOCS 2002: 551-560
  10. A Note on the Representational Incompatibility of Function Approximation and Factored Dynamics. E. Allender, S. Arora, M. Kearns, C. Moore, and A. Russell: Proc. 16th Annual Conference on Neural Information Processing Systems (NIPS), 2002.
  11. Spikernels: Embedding Spiking Neurons in Inner-Product Spaces Lavi Shpigelman, Yoram Singer, Ronny Paz, Eilon Vaadia, NIPS 2002.
  12. Discriminative Binaural Sound Localization Ehud Ben-Reuven and Yoram Singer, NIPS 2002.
  13. Multiclass Learning by Probabilistic Embeddings Ofer Dekel and Yoram Singer, NIPS 2002.
  14. Kernel Design using Boosting Koby Crammer, Joseph Keshet, Yoram Singer, NIPS 2002.
  15. An Efficient PAC Algorithm for Reconstructing a Mixture of Lines Sanjoy Dasgupta, Elan Pavlov, Yoram Singer, ALT 2002.

 

2003-04

  1. Better streaming algorithms for clustering problems. M. Charikar, L. O'Callaghan, R. Panigrahy: STOC 2003: 30-39
  2. Approximation Schemes for Degree-Restricted MST and Red-Blue Separation Problem. S. Arora, K. Chang: ICALP 2003: 176-188
  3. Private Circuits: Securing Hardware against Probing Attacks. Y. Ishai, A. Sahai, D. Wagner: CRYPTO 2003: 463-481
  4. On the Impossibility of Dimension Reduction in l1. B. Brinkman, M. Charikar: FOCS 2003: 514-523, (best paper award).
  5. Clustering with Qualitative Information. M. Charikar, V. Guruswami, A. Wirth: FOCS 2003: 524-533
  6. Frugality in path auctions. E. Elkind,  A. Sahai, K. Steiglitz: SODA 2004: 701-709
  7. Positive Results and Techniques for Obfuscation. B. Lynn, M. Prabhakaran, A. Sahai: EUROCRYPT 2004: 20-39
  8. Smooth Epsilon-Insensitive Regression by Loss Symmetrization Ofer Dekel, Shai Shalev-Shwartz, Yoram Singer, COLT 2003.
  9. Learning Algorithms for Enclosing Points in Bregmanian Spheres Koby Crammer and Yoram Singer, COLT 2003.
  10. Feature-Rich Part-of-Speech Tagging with a Cyclic Dependency Network Kristina Toutanova, Dan Klein, Christopher D. Manning, Yoram Singer, NAACL 2003.

 

 

2004

  1. Expander flows, geometric embeddings, and approximate graph partitioning. S. Arora, S. Rao, and U. Vazirani. Proc. ACM Symposium on Theory of Computing, 2004, (best paper award).
  2. Batch Codes and Their Applications. Y. Ishai, E. Kushilevitz, R. Ostrovsky, A. Sahai: Proc. ACM Symposium on Theory of Computing, 2004.
  3. New Notions of Security: Achieving Universal Composability without Trusted Setup. M. Prabhakaran, A. Sahai: Proc. ACM Symposium on Theory of Computing, 2004.
  4. Approximating quadratic programs: extending Grothendieck's inequality. M. Charikar, A. Wirth, submitted.
  5. \sqrt{logn} approximation to SPARSEST CUT can be computed in O(n^2) time. S. Arora, E. Hazan, and S. Kale. submitted.
  6. Learning arbitrary mixtures of gaussians. S. Arora and R. Kannan. To appear in Annals of Applied Probability. (prelim version in Proc. ACM STOC 2001.)
  7. Online and Batch Learning of Pseudo-Metrics  S. Schwartz, Y. Singer, A. Ng ICML2004
  8. Leveraging the Margin More Carefully Nir Krause and Yoram Singer, ICML 2004 (to appear).
  9. Large Margin Hierarchical Classification Ofer Dekel, Joseph Keshet, Yoram Singer, ICML 2004 (to appear).
  10. Online Passive-Aggressive Algorithms Koby Crammer, Ofer Dekel, Shai Shalev-Shwartz, Yoram Singer NIPS 2004, (to appear).
  11. Online Classification on a Budget Koby Crammer, Jaz Kandola, Yoram Singer NIPS 2004, (to appear).
    12. 2003

 

Undergraduate projects (done at Princeton University)

  1. Compact Representation of Large/Complex Data Sets, E. Huang (Fall 2003).  
  2. Mathematical Programming Relaxations of the Linear Ordering Problem, L. Orecchia (Fall 2003).
  3. Online Clustering of Linguistic Data, L. Reyzin (Spring 2004).
  4. Computer Input Methods for Chinese through Pinyin Segmentation, B. Liu (Spring 2004).
  5. A computational approach to proving bounds on Grothendieck's constant, M. Dinitz (Spring 2004).
  6. Lower Bounds on Embeddings of Planar Graphs into the l1 metric, R. Bhargava (senior thesis 2003-04).