Publications of Ramamohan Paturi

The publications are in reverse chronological order and are classified along the following categories.

Exact complexity and satisfiability

  1. Russell Impagliazoo, Shachar Lovett, Ramamohan Paturi, and Stefan Schneider, 0-1 Integer Programming with a Linear Numberof Constraints, manuscript
  2. Russell Impagliazzo and Ramamohan Paturi, Exact Complexity and Satisfiability, invited paper, Proceedings of the IPEC 2013: 8th International Symposium on Parameterized and Exact Computation, Nice, France, Lecture Notes in Computer Science, vol. 8246, Springer, 2013.
    Paper presented in connection with the award of the Nerode Prize.
  3. Russell Impagliazzo, Ramamohan Paturi, and Stefan Schneider, A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits, Proceedings of the 54th IEEE Foundations of Computer Science 2013, Berkeley, USA, 2013.
  4. Marek Cygan, Holger Dell, Daniel Lokshtanov, Daniel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wählstrom, On Problems as Hard as CNF-SAT, Conference on Computational Complexity, CCC 2012, Porto, Portugal, June 26-29.
  5. Russell Impagliazzo, William Matthews, Ramamohan Paturi, A Satisfiability Algorithm for $AC^0$, Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), Kyoto, Japan, January 17-19, pp 961--972, 2012.
  6. Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi, On the Exact Complexity of Evaluating Quantified k-CNFs, Algorithmica, April 2012, Springer-Verlag.
    Preliminary version appeared in Proceedings of the 5th International Conference on Parameterized and Exact Computation (IPEC 2010), Chennai, India, December 13-15, Lecture Notes in Computer Science, vol. 6478, pp 50--59, Springer 2010.
  7. William Matthews and Ramamohan Paturi. Uniquely Satisfiable k-SAT Instances with Almost Minimal Occurrences of Each Variable, Proceedings of the Thirteenth International Conference on Theory and Applications of Satisfiability Testing---SAT 2010, UK, July 11-14, 2010, Lecture Notes in Computer Science, Volume 6175, pp 369--374
  8. R. Paturi, Exact Algorithms and Complexity (abstract of invited talk), Proceedings of the Thirteenth International Conference on Theory and Applications of Satisfiability Testing---SAT 2010, UK, July 11-14, 2010, Lecture Notes in Computer Science, Volume 6175, pp 8--9
  9. R. Paturi, P. Pudlák, On the Complexity of Circuit Satisfiability, Proceedings of the 42nd ACM Symposium on Theory of Computing, pages 241--250, 2010.
  10. Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi, The Complexity of Satisfiability of Small Depth Circuits, Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC 2009), Copenhagen, Denmark, September 10-11, Lecture Notes in Computer Science 5917, pp 75--85, 2009.
  11. Chris Calabro and Ramamohan Paturi, k-SAT is no Harder Than Decision-Unique-k-SAT, Proceedings of the Fourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18-23, Lecture Notes in Computer Science 5675, pp 59--70, 2009.
  12. Chris Calabro, Russell Impagliazzo, Ramamohan Paturi, A Duality between Clause Width and Clause Density for SAT, 21st Annual IEEE Conference on Computational Complexity (CCC'06), 2006.
  13. Ramamohan Paturi, Pavel Pudláak, Michael E. Saks, Francis Zane, Backtracking Based k-SAT Algorithms, (invited to write an article based on an earlier journal paper which is regarded as one of the high-impact algorithms of the last decade by the editors of the volume). Encyclopedia of Algorithms (Ed. Ming-Yang Kao), 2008, Springer-Verlag.
  14. C. Calabro, R. Impagliazzo, V. Kabanets, and R. Paturi, The complexity of Unique k-SAT: An isolation lemma for k-CNFs, Journal of Computer and Systems Sciences, Volume 74, Issue 3, Pages 386-393, May 2008.
    Preliminary version appeared in Proceedings of the Eighteenth IEEE Conference on Computational Complexity, 135-144, 2003.
    (deemed as among the best papers in the conference)
  15. Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane, An improved exponential-time algorithm for k-SAT, Journal of the ACM, Vol. 52, Issue 3, pp 337-364, May 2005.
    Preliminary version appeared in Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, pages 628-637, 1998.
  16. R. Impagliazzo and R. Paturi, On the Complexity of k-SAT, Journal of Computer and Systems Sciences, 62(2):367-375, Mar 2001.
    Preliminary version appeared in Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity, pages 237-240, 1999.
  17. R. Impagliazzo, R. Paturi and F. Zane, Which Problems have Strongly Exponential Complexity?, Journal of Computer and System Sciences, Volume 63, Issue 4, Pages 512-530, December 2001.
    Preliminary version appeared in Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, pp 653-662, 1998.
  18. R. Paturi, P. Pudlák, and F. Zane, Satisfiability Coding Lemma, Chicago Journal of Theoretical Computer Science, 1999.
    Preliminary version appeared in Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 566-574, 1997.

Social networks and game theory

  1. Moshe Hoffman, Daniel Moeller, and Ramamohan Paturi, Jealousy Graphs: Structure and Complexity of Decentralized Stable Matching, Proceedings of WINE 2013: The 9th Conference on Web and Internet Economics, Cambridge, USA, 2013.
  2. Nuh Aygun Dalkiran, Moshe Hoffman, Ramamohan Paturi, Daniel Ricketts, and Andrea Vattani, Common Knowledge and State-dependent Equilibria, Proceedings of SAGT 2012 (Symposium on Algorithmic Game Theory 2012), Barcelona, Spain.
  3. Lorenzo Coviello, Massimo Franceschetti, Mathew D. McCubbins, Ramamohan Paturi, and Andrea Vattani, Human Matching Behavior in Social Networks: An Algorithmic Perspective, PLoS ONE 7(8): e41900. doi:10.1371/journal.pone.0041900, August 2012. (journal paper)
  4. Daniel P. Enemark, Mathew D. McCubbins, Ramamohan Paturi, and Nicholas Weller, Does more connectivity help groups to solve social problems?, Proceedings of the 12th ACM conference on Electronic commerce (EC 2011), San Jose, California, 2011, pp 21--26.
    Preliminary version appeared in Workshop on Information in Networks 2010, September 24-25th, 2010, New York University School of Business.
  5. Amos Israeli, Mathew McCubbins, Ramamohan Paturi and Andrea Vattani. Low Memory Distributed Protocols for 2-Coloring, Proceedings of the 12th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2010), New York City, USA, September 20--22, 2010.
  6. Mathew McCubbins, Ramamohan Paturi, Nicholas Weller, Networked Coordination: Effect of Network Structure Human Subjects' Ability to Solve Coordination Problem, American Politics Research, September 2009, vol. 37, no. 5, pages 899-920.

Learning algorithms

  1. Lucia Batman, Russell Impagliazzo, Cody Murray, and Ramamohan Paturi, Finding heavy hitters from lossy or noisy data, Proceedings of RANDOM 2013: 17th International Workshop on Randomization and Computation, Berkeley, CA, Lecture Notes in Computer Science,, vol. 8096, pp 347--362, Springer, 2013.
  2. R. Paturi, S. Rajasekaran, and J. Reif, The Light Bulb Problem, Information and Computation, vol. 117, No. 2, 187--192, 1995.
    Preliminary version appeared in Proceedings of the Second Annual Workshop on Computational Learning Theory, pp 261--268, 1989.
  3. J. Komlós, and R. Paturi, Convergence Analysis of Associative Memory Models, a chapter in the book: Associative Neural Memories: Theory and Implementation, edited by Mohamad H. Hassoun, Oxford University Press, 1993.
  4. J. Komlós, and R. Paturi, Effect of Connectivity in Associative Memory Models, Journal of Computer and System Sciences, vol.47, pp. 350-373, 1993.
    Preliminary version appeared in Proceedings of the IEEE Symposium on Foundations of Computer Science, pp 138--147, 1988.
  5. J. Komlós, and R. Paturi, Convergence Results in an Associative Memory Model, Neural Networks, Vol. 1, No. 3, pp 239--250, 1988.
    An abstract of this paper is published on invitation in the Proceedings of First Workshop on Computational Learning Theory, pp. 417--418, 1988.

Lower bounds

  1. Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane, An improved exponential-time algorithm for k-SAT, Journal of the ACM, Vol. 52, Issue 3, pp 337-364, May 2005.
    Preliminary version appeared in Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, pages 628-637, 1998.
  2. R. Impagliazzo, R. Paturi and F. Zane, Which Problems have Strongly Exponential Complexity?, Journal of Computer and System Sciences, Volume 63, Issue 4, Pages 512-530, December 2001.
    Preliminary version appeared in Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, pp 653-662, 1998.
  3. R. Paturi, P. Pudlák, and F. Zane, Satisfiability Coding Lemma, Chicago Journal of Theoretical Computer Science, 1999.
    Preliminary version appeared in Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 566-574, 1997.
  4. R. Paturi and P. Pudlák, Circuit lower bounds and linear codes, Notes of Mathematical Seminars of St.Petersburg Department of Steklov Institute of Mathematics, vol. 316, Teoria slozhnosti vychislenij IX, E. A. Hirsch editor, 2004, pp.188-204. Translations as well as English language papers will be republished in the Journal of Mathematical Sciences, Kluwer Publications.
  5. R. Paturi, M.E. Saks, and F. Zane, Exponential Lower Bounds for Depth 3 Boolean Circuits, Computational Complexit, Volume 9, Number 1, pp 1--15, November, 2000.
    Preliminary version appeared in 29th annual ACM Symposium on Theory of Computing, 1997, 96--91.
  6. R. Paturi and F. Zane, Dimension of Projections in Boolean Functions, SIAM Journal on Discrete Mathematics, vol.11, no.4, pages 624-632, November 1998.
  7. R. Impagliazzo, R. Paturi and M.E. Saks, Size--Depth Trade--offs for Threshold Circuits, SIAM Journal of Computing, Vol. 26, No. 3, pp 693-707, 1997.
    Preliminary version appeared in 1993 ACM Symposium on Theory of Computing, pp 541--550, May 1993.
  8. R. Paturi, On the Degree of Polynomials that Approximate Symmetric Boolean Functions, 24th ACM symposium on Theory of Computing, Victoria, British Columbia, 1992, pp 468--474.
  9. R. Paturi, and M. Saks, Approximation of Threshold Circuits by Rational Functions, Information and Computation, vol. 112, No.2, pp. 257--272, August 1994.
  10. R. Paturi and M. Saks, On Threshold Circuits for Parity, 31st IEEE Symposium on Foundations of Computer Science, pp 397--404, October 1990.
    An abstract of this paper is published in the Proceedings of Third Workshop on Computational Learning Theory, COLT'90, pp. 390, 1990.
  11. R. Paturi, J. Simon, J. I. Seiferas, and R. E. Newman-Wolfe, Milking the Aanderaa argument, Information and Computation, vol. 88, pp. 88--104, 1990.
  12. M. Geréeb--Graus, R. Paturi, and E. Szemerédi, There are no p-Complete Families of Symmetric Boolean Functions, Information Processing Letters,, 30, pp 47--49, 1989.
  13. H. J. Karloff, R. Paturi, and J. Simon, Universal Traversal Sequences of Length $n ^ {O (\log n )}$ for Cliques, Information Processing Letters, 28, pp 241--243, 1988.
  14. Paturi, R., and J. Simon, Probabilistic Communication Complexity, Journal of Computer and System Sciences, Vol 33, No.1, pp 106--123, August 1986.
    Preliminary version appeared in Proc. 25th IEEE Foundations of Computer Science, pp 118-126, 1984.
    One of the conference papers selected for publication in the Journal of Computer and System Sciences.
  15. Paturi, R., and J. Simon, Lower Bounds on the Time of Probabilistic on-line Simulations, Proceedings of the 24th IEEE Foundations of Computer Science, pp 343-350, 1983.

Other

  1. K. Levchenko, G. M. Voelker, R. Paturi, and S. Savage. XL: An efficient network routing algorithm. Proceedings of the 2008 ACM SIGCOMM Conference, pages 15--26, 2008.
  2. Kirill Levchenko, Ramamohan Paturi and George Varghese, On the Difficulty of Scalably Detecting Network Attacks, Proceedings of the 11th ACM conference on Computer and communications security, 12-20, 2004.
  3. F. Zane, P. Marchand, R. Paturi, S. Esener, Scalable Network Architectures using the Optical Transpose Interconnection System (OTIS), Journal of Parallel and Distributed Computing, vol.60, no.5, pages 521-538, May 2000.
    Preliminary version presented at 3rd International Conference on Massively Parallel Processing using Optical Interconnections, Oct 27--29, 1996, Maui, Hawaii.
  4. O. Brandman, C. P. Elkan, and R. Paturi, Improved Web Searching Using Neighborhood Ranking, Poster Proceedings of 8th International World Wide Web Conference, Toronto, Canada, May 1999.
  5. B.H. Olson, R. Paturi and S.C. Esener, Bi-orthogonally Accessed 3D 2-Photon Memory for Relational Database Operations, Applied Optics, Vol. 36, No. 17, 3887-3888, 1997.
  6. R.J. Carragher, C.K. Cheng, X.M. Xiong, M. Fujita, and R. Paturi, Solving the Net Matching Problem in High-Performance Chip Design, IEEE Transactions on Computer-Aided Design, vol. 15, no. 8, pp 902-911, 1996.
  7. F. Berman, V. Donaldson, and R. Paturi, Program Speedup in a Heterogeneous Computing System, Journal of Parallel and Distributed Computing, 21, pp 316--322, 1994.
  8. D.-T. Lu, V.H. Ozguz, P.J. Marchand, A.V. Krishnamoorthy, F. Kiamilev, R. Paturi, S.H. Lee, and S.C. Esener, Design Trade--offs in Opto--electronic Parallel Processing Systems using Smart--SLMs, Journal of Optical and Quantum Electronics, 24, S379--S403, 1992.
  9. Ashok V. Krishnamoorthy, Ramamohan Paturi, Matthias Blume, Gregory D. Linden, Lars H. Liden, and Sadik C. Esener, Hardware Trade-off for Boolean Concept Learning, World Congress on Neural Networks 1994, I-551 --- I-559, 1994.
  10. R. Paturi, Dau--Tsuong Lu, Joseph E. Ford, Sadik C. Esener, Sing H. Lee, Parallel Algorithms based on Expander Graphs for Optical Computing, Applied Optics, vol. 30, No. 8, pp. 917--927, March 1991.
    Preliminary version presented at 23rd Asilomar Conference on Signals, Systems and Computers, October 1989. Oral Presentation.
  11. F. Kiamilev, A. Krishnamoorthy, P. Marchand, R. Paturi, S. Esener, and S.H. Lee, Design of Interconnection Networks for Programmable Opto--electronic Multiprocessor Technology, in Conference Record of 1990 International Topical Meeting on Optical Computing, Kobe, Japan, April 8--12, 1990, pp 217--218.
  12. F. Kiamilev, S. C. Esener, R. Paturi, Y. Fainman, P. Mercier, C. C. Guest, and S. H. Lee, Programmable Opto--Electronic Multiprocessors and their Comparison with Symbolic Substitution for Digital Optical Computing and Symbolic Substitution Systems, Optical Engineering, Vol. 28 No.4, pp 396--409, April 1989.