Publications

copyright: In all instances below, the publishers own the copyright and a copy is made available here only for personal, non-commercial use. In many cases, the papers below are substantial extensions of the corresponding conference versions.

• Hellinger Strikes Back: A Note on the Multi-Party Information Complexity of AND. T.S. Jayram. RANDOM 2009.
  
  
• On the Communication Complexity of Read-Once AC^0 Formulae T.S. Jayram, Swastik Kopparty, Prasad Raghavendra. IEEE Conference on Computational Complexity, CCC 2009.
  
  
• Exponential Separation of Quantum and Classical One-Way Communication Complexity. Ziv Bar-Yossef, T.S. Jayram, Iordanis Kerenidis. SIAM Journal on Computing, 2008. Conference version.
  
  
• Tight lower bounds for selection in randomly ordered streams. Amit Chakrabarti, T.S. Jayram, Mihai Patrascu. Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008.
  
  
• Estimating statistical aggregates on probabilistic data streams. T.S. Jayram, Andrew McGregor, S. Muthukrishnan, Erik Vee. Twenty-Sixth ACM Symposium on Principles of Database Systems PODS 2007.
  
  
• OLAP over uncertain and imprecise data. Douglas Burdick, Prasad M. Deshpande, T.S. Jayram, Raghu Ramakrishnan, Shivakumar Vaithyanathan. VLDB Journal 2007. Conference version.
  
  
• Lower bounds for randomized read/write stream algorithms. Paul Beame, T.S. Jayram, Atri Rudra. 39th Annual ACM Symposium on Theory of Computing, STOC 2007.
  
  
• Efficient Aggregation Algorithms for Probabilistic Data. T.S. Jayram, Satyen Kale, Erik Vee. Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007.
  
  
• Estimating the Sortedness of a Data Stream. Parikshit Gopalan, T.S. Jayram, Robert Krauthgamer, Ravi Kumar. Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007.
  
  
• Index Coding with Side Information. Ziv Bar-Yossef, Yitzhak Birk, T.S. Jayram and Tomer Kol 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS) 2006.
  
  
• Efficient Allocation Algorithms for OLAP Over Imprecise Data. Douglas Burdick, Prasad M. Deshpande, T.S. Jayram, Raghu Ramakrishnan, Shivakumar Vaithyanathan. 32nd International Conference on Very Large Data Bases (VLDB) 2006.
  
  
• The Containment Problem for REAL Conjunctive Queries with Inequalities. T.S. Jayram, Phokion G. Kolaitis, Erik Vee. Twenty-Fifth ACM Symposium on Principles of Database Systems (PODS) 2006.
  
  
• Avatar Information Extraction System. T.S. Jayram, Rajasekar Krishnamurthy, Sriram Raghavan, Shivakumar Vaithyanathan, Huaiyu Zhu. IEEE Data Engineering Bulletin 29(1):40-48, 2006.
  
  
• OLAP Over Uncertain and Imprecise Data. Doug Burdick, Prasad Deshpande, T.S. Jayram, Raghu Ramakrishnan, Shivakumar Vaithyanathan. 31st International Conference on Very Large Data Bases (VLDB) 2005..
  
  
• The sketching complexity of pattern matching. Ziv Bar-Yossef, T.S. Jayram, Robert Krauthgamer, Ravi Kumar. 8th International Workshop on Randomization and Computation (RANDOM) 2004..
  
  
• Approximating edit distance efficiently. Ziv Bar-Yossef, T.S. Jayram, Robert Krauthgamer, Ravi Kumar. 45th Symposium on Foundations of Computer Science (FOCS) 2004..
  
  
• Exponential separation of quantum and classical one-way communication complexity. Ziv Bar-Yossef, T.S. Jayram, Iordanis Kerenidis. 36th Annual ACM Symposium on Theory of Computing (STOC) 2004. ECCC version
  
  
• Generalized opinion pooling. Ashutosh Garg, T.S. Jayram, Shivakumar Vaithyanathan, Huaiyu Zhu. 8th International Symposium on Artificial Intelligence and Mathematics (AI&M) 2004.
  
  
• Cell-probe lower bounds for the partial match problem. T.S. Jayram, Subhash Khot, Ravi Kumar, Yuval Rabani. Journal of Computer and System Sciences (JCSS) 2004 (Special issue for 35th ACM Symposium on Theory of Computing (STOC) 2003).
  
  
• Two applications of information complexity. T.S. Jayram, Ravi Kumar, D. Sivakumar. 35th ACM Symposium on Theory of Computing (STOC) 2003.
  
  
• Approximate counting of inversions in a data stream. Miklós Ajtai, T.S. Jayram, Ravi Kumar and D. Sivakumar. Proc. 34th Annual ACM Symposium on Theory of Computing (STOC).
  
  
• Information theory methods in communication complexity. Ziv Bar-Yossef, T.S. Jayram, Ravi Kumar and D. Sivakumar. 17th IEEE Conference on Computational Complexity (CCC) 2002.
  
  
• An information statistics approach to data stream and communication complexity. Ziv Bar-Yossef, T.S. Jayram, Ravi Kumar, D. Sivakumar. 43rd IEEE Foundations of Computer Science (FOCS) 2002.
  
  
• Counting distinct elements in a data stream. Ziv Bar-Yossef, T.S. Jayram, Ravi Kumar, D. Sivakumar, Luca Trevisan. 6th International Workshop on Randomization and Computation (RANDOM) 2002.
  
  
• Using control theory to achieve service level objectives in performance management. Sujay S. Parekh, Neha Gandhi, Joseph L. Hellerstein, Dawn M. Tilbury, T.S. Jayram, Joseph P. Bigus. Real-Time Systems Journal.
  
  
• Online server allocation in a server farm via benefit task systems. T.S. Jayram, Tracy Kimbrel, Robert Krauthgamer, Baruch Schieber, Maxim Sviridenko. STOC 2001.
  
  
• Tighter bounds on preemptive job shop scheduling with two machines. Eric J. Anderson, T.S. Jayram, Tracy Kimbrel. Computing 2001.
  
  
• Time-space tradeoffs for branching programs. Paul Beame, T.S. Jayram, Michael E. Saks. JCSS 2001.
  
  
• Recognizing end-user transactions in performance management. Joseph L. Hellerstein, T.S. Jayram, Irina Rish. AAAI 2000.
  
  
• Analysis of Large-Scale Distributed Information Systems. Joseph L. Hellerstein, T.S. Jayram, Mark S. Squillante. MASCOTS 2000.
  
  
• On separating the read-k-times branching program hierarchy. Jayram S. Thathachar. STOC 1998.
  
  
• On the Limitations of Ordered Representations of Functions Jayram S. Thathachar. CAV 1998.
  
  
• Efficient branching programs for threshold and mod functions Jayram S. Thathachar. JCSS 1998.