Complexity:
· Index Coding with Side Information
with Yitzhak (Tsahi) Birk, T. S. Jayram, and Tomer Kol.
FOCS 2006
[full version] [proceedings version]
· The Sketching Complexity of Pattern Matching
with T.S. Jayram, Robert Krauthgamer, and Ravi Kumar.
RANDOM 2004
[proceedings version]
· Exponential Separation of Quantum and Classical One-Way Communication Complexity
with T.S. Jayram and Iordanis Kerenidis.
SICOMP 2008, STOC 2004.
[journal version] [proceedings version]
· Sampling Lower Bounds via Information Theory
STOC 2003
[full version] [proceedings version] [slides]
· Information Statistics Approach to Data Stream and Communication Complexity
with T.S. Jayram, Ravi Kumar, and D. Sivakumar.
JCSS 2004, FOCS 2002.
[journal version] [proceedings version] [slides]
· Information Theory Methods in Communication Complexity
with T.S. Jayram, Ravi Kumar, and D. Sivakumar.
CCC 2002
[full version] [proceedings version]
· Streaming Computation of Combinatorial Objects
with Omer Reingold, Ronen Shaltiel, and Luca Trevisan
CCC 2002
[full version] [proceedings version] [slides]
· Sampling Algorithms: Lower Bounds and Applications
with Ravi Kumar, and D. Sivakumar.
STOC 2001
[full version] [proceedings version] [slides]
· Deterministic Amplification of Space Bounded Probabilistic Algorithms
with Oded Goldreich and Avi Wigderson.
CCC 1999
[proceedings version] [slides]
· Pointer Jumping Requires Concurrent Read
with Noam Nisan.
STOC 1997
[full version]
