Faculty Profile

Ruta Mehta

Computer Science
Ruta Mehta
Ruta Mehta
Assistant Professor
3218 Siebel Center for Comp Sci
201 N. Goodwin Ave.
Urbana Illinois 61801
(217) 300-4650

Primary Research Area

  • Theory and Algorithms

Education

  • Doctor of Philosophy, Computer Science and Engineering, Indian Institute of Technology, Bombay. 2012. Advisor: Prof. Milind Sohoni
  • Masters of Technology,Computer Science and Engineering, Indian Institute of Technology, Bombay, 2005
  • Bachelor of Engineering, Computer Engineering, Maharaja Saiyajirao University (MSU) Baroda, 2003

Biography

I am currently an Assistant Professor in the Department of Computer Science. Prior to joining UIUC, I did postdoc at Simons Institute for Theory of Computing at UC Berkeley (Aug'15 to Dec'15), and in College of Computing at Georgia Tech (Aug'12 to July'15, advisor: Prof. Vijay V. Vazirani). I received my Ph.D. in computer science from IIT-Bombay under the supervision of Prof. Milind Sohoni and Prof. Bharat Adsul, in August 2012. My Ph.D. thesis titled "Nash Equilibrium Computation in Various Games" won the ACM India Doctoral Dissertation Award, 2012.

Academic Positions

  • Assistant Professor, Dept of Computer Science, University of Illinois at Urbana-Champaign. 2016 - Present
  • Postdoctoral Fellow, Simons Institute for Theory of Computing, University of California at Berkeley. July'15 - Dec'15. Host: Prof. Allistair Sinclair.
  • Postdoctoral Fellow, College of Computing, Georgia Institute of Technology. Sept'12 - July'15. Host: Prof. Vijay V. Vazirani
  • Software Engineer and Developer, Sybase India, Aug'05 - July'07

For more information

Professional Registrations

  • ACM membership since 2017

Other Professional Activities

  • Committees Served on:        - Undergraduate Study Committee at UIUC, 2016-now.       - Diversity Committee, 2019-now.        - PhD thesis of Sadra Yazdanbod, 2018 (Georgia Tech, Advisor: Vijay Vazirani)        - PhD thesis of Haiming Jin, 2017 (U. of I. at Urbana-Champaign, Advisor: Klara Nahrstedt)        - PhD thesis proposal of Vivek Madan, 2017 (U. of I. at Urbana-Champaign, Advisor: Chandra Chekuri)        - PhD thesis of Ioannis Panageas, 2016 (Georgia Tech, Advisor: Prasad Tetali)        - PhD thesis of Eric Chastain, 2016 (Rutgers U., Advisor: Eric Allender)        - Research scholar representative at IIT-Bombay for the year 2008-2009.  
  • Journal Reviewing: INFORMS￿MOR,￿ INFORMS OR, J. of ACM, SAIM J. on Comp., Games and Econ. Behavior, Int. J. Game Theory, Algorithmica, Trans. on Econ & Comp., Theory of Comp. ￿

Resident Instruction

  • CS598 RM: Topics on Algorithmic Game Theory, Fall'18
  • CS 473: Theory II (Algorithms), Spring'18 (40+ students completed the course)
  • CS598 RM: Topics on Algorithmic Game Theory, Spring'17 (Listed in the "Instructors rated as excellent by students")
  • CS473: Theory II (Algorithms), Fall'16 (60+ students completed the course)
  • CS598 RM: Topics on Algorithmic Game Theory, Spring'16

Course Development

  • CS598 RM: Topics on Algorithmic Game Theory

Other Undergraduate Advising Activities

  • Shivam Gupta, Illinois engineering scholarship for 2017-2018, Franz Hohn and JP Nash scholarship for 2015-2016. Advising period: 2017 - 2018 (Published a paper in AAMAS'18)

Research Statement

My main research interests lie in the areas of algorithmic game theory, mathematical economics, and in design of efficient algorithms. I am interested in exploring the computability of equilibria, both market and Nash, under various settings, and also understanding the impact of strategic behavior in multi-agent situations. Currently, I am exploring problems from dynamic matching, fair division of scarce resources, and market design for cloud computing. In addition I am exploring avenues for interdisciplinary applications of these tools to genetic evolution, machine learning and dynamical systems.

Research Interests

  • Algorithmic Game Theory: Equilibrium Computation and Complexity, Smoothed Analysis, Learning in Games
  • Strategic Analysis of Games and Markets
  • Game Theoretic Analysis of Genetic Diversity

Research Areas

Selected Articles in Journals

  • A simplex-like algorithm for linear Fisher markets. Adsul, Bharat, Ch Sobhan Babu, Jugal Garg, Ruta Mehta, and Milind Sohoni. JSTOR Current Science (2012), 103(9), 1033-1042.
  • A complementary pivot algorithm for market equilibrium under separable, piecewise-linear concave utilities. Jugal Garg, Ruta Mehta, Milind Sohoni, and Vijay V. Vazirani. SIAM Journal on Computing (2015), 44(6), 1820-1847.
  • Dichotomies in Equilibrium Computation and Membership of PLC Markets in FIXP. Jugal Garg, Ruta Mehta, and Vijay V. Vazirani. ELSEVIER Theory of Computing (2016), 12(1), 1-25.
  • An incentive compatible, efficient market for air traffic flow management. Ruta Mehta and Vijay V. Vazirani. ELSEVIER Theoretical Computer Science (2018).
  • Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm. Jugal Garg, Ruta Mehta, and Vijay Vazirani. INFORMS Mathematics of Operations Research (2018), 43(3).
  • Constant Rank Bimatrix Games are PPAD-hard. Ruta Mehta. SIAM Journal on Computing. 47(5): 1858￿1887 (2018). (Invited to the special issue on the STOC'14)
  • EXISTS-R-Completeness for Decision Versions of Multi-Player (Symmetric) Nash Equilibria. Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod, ACM Transactions on Economics and Computation (2018), 6(1).

Articles in Conference Proceedings

  • Bilinear Games: Polynomial Time Algorithms for Rank Based Subclasses. Jugal Garg, Albert X. Jiang, and Ruta Mehta. In Proceedings of the International Workshop on Internet and Network Economics (WINE), 399--407, 2011. Springer. (31% acceptance rate)
  • The Weighted Majority Algorithm does not Converge in Nearly Zero-sum Games. Maria Florina Balcan, Florin Constantin, and Ruta Mehta. In ICML 2012 workshop on Markets Mechanisms and Multi-Agent Models, 2012. (27% acceptance rate)
  • Towards Polynomial Simplex-Like Algorithms for Market Equilibria. Jugal Garg, Ruta Mehta, Milind Sohoni and Nisheeth Vishnoi. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1226--1242, 2013. ACM-SIAM. (29% acceptance rate)
  • To Save Or Not To Save: The Fisher Game. Ruta Mehta, Nithum Thain, Laszlo A. Vegh, and Adrian Vetta. In Proceedings of the 10th International Conference on Web and Internet Economics (WINE), 294--307, 2014. Springer. (29% acceptance rate)
  • Learning Economic Parameters from Revealed Preferences. Maria-Florina Balcan, Amit Daniely, Ruta Mehta, Ruth Urner, and Vijay V. Vazirani. In Proceedings of the 10th International Conference on Web and Internet Economics (WINE), 338--353, 2014. Springer. (29% acceptance rate)
  • ETR-Completeness of Decision Versions of 3-Nash. Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), 554--566, 2015. Springer. (28% acceptance rate)
  • Natural Selection as an Inhibitor of Genetic Diversity: Multiplicative Weights Update Algorithm and a Conjecture of Haploid Genetics. Ruta Mehta, Ioannis Panageas and Georgios Piliouras. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (ITCS), 73--73, 2015. (28% acceptance rate)
  • Settling Some Open Problems on Symmetric Nash Equilibria. Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod. In Proceedings of the 8th International Symposium on Algorithmic Game Theory (SAGT), 272--284, 2015. Springer. (34% acceptance rate)
  • Multilinear Games. Hau Chu, Albert Jiang, Kevin Leyton-Brown, and Ruta Mehta. In Proceedings of the12th International Conference on Web and Internet Economics (WINE), 44-58, 2016. Springer. (39% acceptance rate)
  • The Complexity of Genetic Diversity: Sex with Two Chromosomes is Advantageous but Unpredictable. Ruta Mehta, Ioannis Panageas, Georgios Piliouras and Sadra Yazdanbod. In Proceedings of the 24th Annual European Symposium on Algorithms (ESA), 65:1--65:17, 2016. LIPIcs-Leibniz International Proceedings in Informatics. (27% acceptance rate)
  • Get Me to My GATE On Time: Efficiently Solving General-Sum Bayesian Threat Screening Games. Aaron Schlenker, Matthew Brown, Arunesh Sinha, Milind Tambe, and Ruta Mehta. In Proceedings of the 22nd European Conference on Arti cial Intelligence (ECAI), 1476--1484, 2016. (27% acceptance rate)
  • To Give or not to Give: Fair Division with Strict Preferences. Simina Branzei, Yuezhou Lv, and Ruta Mehta. In Proceedings of the 25th International Joint Conference on Arti cial Intelligence (IJCAI), 123--129, 2016. AAAI Press. (24% acceptance rate)
  • An Incentive Compatible, Efficient Market for Air Trac Flow Management. Ruta Mehta, and Vijay V. Vazirani. In Proceedings of the 23rd International Computing and Combinatorics Conference (COCOON), 407-- 419, 2017. Springer. (43% acceptance rate)
  • Nash Social Welfare Approximation for Strategic Agents. Simina Branzei, Ruta Mehta, and Vasilis Gkatzelis. In Proceedings of the 2017 ACM Conference on Economics and Computation (EC), 611--628, 2017. ACM. (29% acceptance rate)
  • Mutation, Sexual Reproduction and Survival in Dynamic Environments. Ruta Mehta, Ioannis Panageas, Georgios Piliouras, Prasad Tetali, and Vijay V. Vazirani. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS), 2017. (35% acceptance rate)
  • Settling the Complexity of Leontief and PLC Exchange Markets under Exact and Approximate Equilibria. Jugal Garg, Ruta Mehta, Vijay V. Vazirani and Sadra Yazdanbod. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 890--901, 2017. ACM. (24% acceptance rate)
  • A New Class of Combinatorial Markets with Covering Constraints: Algorithms and Applications. Nikhil Devanur, Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2311--2325, 2018. ACM-SIAM. (33% acceptance rate)
  • Sum-of-Squares Meets Nash: Lower Bounds for Finding Any Equilibrium. Pravesh Kothari and Ruta Mehta. In Proceedings of the 50th Annual Symposium on the Theory of Computation (STOC), 1241--1248, 2018. ACM. (26.6% acceptance rate)
  • Nash Equilibrium Computation in Resource Allocation Game. Shivam Gupta and Ruta Mehta. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 1953-1955, 2018. ACM. (18% acceptance rate)
  • Universal Growth in Production Economies. Simina Branzei, Ruta Mehta, and Noam Nisan. In Proceedings of the 32nd Annual Conference on Neural Information Processing Systems (NIPS), forthcoming, 2018. ACM. (21% acceptance rate)
  • Social Welfare and Profi t Maximization from Revealed Preferences. Ziwei Ji, Ruta Mehta, and Matus Telgarsky. In Proceedings of the 14th Conference on Web and Internet Economicsn (WINE), forthcoming, 2018. ACM. (30% acceptance rate)

Pending Articles

  • Online Revenue Maximization for Server Pricing. Shant Boodaghians, Federico Fusco, Stefano Leonardi, Yishay Mansour and Ruta Mehta. Preprint, 2019.
  • Games that (Busy) Neighbors Play. Wei-Chun Lee, Vasileios Livanos, Ruta Mehta, and Hari Sundaram. Preprint, 2018.
  • Eliciting Binary Performance Metrics. Gaurush Hiranandani, Shant Boodaghians, Ruta Mehta, and Oluwasanmi Koyejo. Accepted to the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS), 2019.
  • End of Potential Line. John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani. Preprint, 2018.
  • Smoothed Efficient Algorithms and Reductions for Network Coordination Games. Shant Boodaghians, Rucha Kulkarni, and Ruta Mehta. Preprint, 2018.

Invited Lectures

Patents

Conferences Organized or Chaired

  • Co-organized Game Theory Workshop (14 - 17 Dec, 2015), as a part of Combinatorial Optimization trimester at Hausdor Center for Mathematics, Universitat Bonn, Germany.
  • Chaired WINE, 2017 Tutorial Session.
  • Co-organized AGT Mentoring Workshop co-located with the 19th ACM Conference on Economics and Computation, June 18, 2018, Cornell University, Ithaca, USA.

Other Scholarly Activities

  • Journal Reviewing: INFORMS￿Mathematics of Operations Research,￿ INFORMS Operations Research, Journal of ACM, SAIM Journal on Computing, Games and Economic Behavior, International Journal Game Theory, Algorithmica, Trans. on Econ & Comp., Theory of Computing
  • Panels: Women in computing for the admitted female students visit 2016, 2017.
  • On Conference Program Committees: ACM Conference on Economics and Computations (EC) (2019) (2016-18 secondary PC); International Colloquium on Automata, Languages and Programming (ICALP) (2019); Innovations in Theoretical Computer Science (ITCS) (2018, 2016); The Web Conference (2018) (2015 poster session); International Symposium on Algorithmic Game Theory (SAGT) (2018,2016); SIAM: ACM-SIAM Symposium on Discrete Algorithms (SODA) (2017); IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) (2017, 2015); Annual IEEE Symposium on Foundations of Computer Science (FOCS) (2015).

Service on Department Committees

  • PhD thesis proposal committee of Vivek Madan, 2017 (Advisor: Chandra Chekuri)
  • PhD thesis committee of Haiming Jin, 2017 ( Advisor: Klara Nahrstedt)
  • Panels: Women in computing for the admitted female students visit 2016, 2017.
  • The undergraduate study committee, 2016- now.
  • Outreach Committee, 2017 - 2018.
  • Diversity Committee, 2019 - now.

Service to Federal and State Government

  • NSF proposal review panel for CISE, 2017

Other Outside Service

  • PhD thesis of Ioannis Panageas, 2016 (Georgia Tech, Advisor: Prasad Tetali)
  • PhD thesis of Eric Chastain, 2016 (Rutgers U., Advisor: Eric Allender)
  • PhD thesis of Sadra Yazdanbod, 2018 (Georgia Tech, Advisor: Vijay Vazirani)

Honors

  • Outstanding Post-Doctoral Researcher Award, College of Computing, Georgia Tech. (2014)
  • Rising Stars in EECS, 2013. (2013)
  • Excellence in Ph.D. Thesis Award, 2012, IIT-Bombay. (2012)
  • First ACM India Doctoral Dissertation Award 2012 . (2012)
  • Google India Anita Borg Memorial Scholarship 2012. (2012)
  • Part of the China Theory Week 2012, hosted by Aarhus University, Denmark. (2012)
  • IBM PhD Award in 2010 . (2010)
  • IBM PhD Fellowship for the year 2009-2010. (2009)

Teaching Honors

  • Teachers Rated as Excellent (Spring'17)

Research Honors

  • NSF CAREER Award (Jan'18)