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
  • Masters of Technology,Computer Science and Engineering, Indian Institute of Technology, Bombay, 2005
  • Bachelor of Engineering, Computer Engineering, Maharaja Saiyajirao University (MSU) Baroda, 2003

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
  • Postdoctoral Fellow, College of Computing, Georgia Institute of Technology. Sept'12 - July'15
  • Software Engineer and Developer, Sybase India, Aug'05 - July'07

For more information

Professional Registrations

  • Program Committee: EC'19 (Senior PC), ICALP'19, EC'18, ITCS'18, WWW'18, SAGT'18, SODA'17, EC'17, FSTTCS'17, ITCS'16, EC'16, SAGT'16, FOCS'15, FSTTCS'15, and WWW'15 (poster).
  • Review Panel: NSF AiTF Panel, 2017.
  • Chair: WINE, 2017 Tutorial Session.
  • Panel Participation: Panel on women in computing for the admitted female students visit 2016, 2017.
  • ￿(Co)Organized Workshops and Events: (1) AGT Mentoring Workshop co-located with the 19th ACM Conference on Economics and Computation, June 18, 2018, Cornell University, Ithaca, USA. (2) A discussion on Career Advice for Graduate Students at the 18th ACM Conference on Economics and Computation, June 26 - 30 2017, MIT. (3) Game Theory Workshop (14 - 17 Dec, 2015), as a part of Combinatorial Optimization trimester at Hausdor Center for Mathematics, Universitat Bonn, Germany.

Resident Instruction

  • Algorithmic Game Theory, Fall'18
  • Theory II (Algorithms), Spring'18
  • Algorithmic Game Theory, Spring'17
  • Theory II (Algorithms), Fall'16
  • Topics on Algorithmic Game Theory, Spring'16

Course Development

  • Algorithmic Game Theory

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

  • Constant Rank Bimatrix Games are PPAD-hard. SIAM Journal on Computing. Forthcoming.
  • An incentive compatible, efficient market for air traffic flow management. Mehta, Ruta, 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).
  • 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).
  • 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.
  • 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.
  • 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.

Articles in Conference Proceedings

  • 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 Economics, forthcoming, 2018. ACM.
  • Universal Growth in Production Economies. Simina Branzei, Ruta Mehta, and Noam Nisan. In Proceedings of the 32nd Annual Conference on Neural Information Processing Systems, forthcoming, 2018. ACM.
  • 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.
  • 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.
  • Maximizing Profi t with Convex Costs in the Random-order Model. Anupam Gupta, Ruta Mehta, and Marco Molinaro. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP), 71:1￿71:14, 2018. LIPICS.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • Constant Rank Bimatrix Games are PPAD-hard. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), 545--554, 2014. ACM.
  • Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions. Jugal Garg, Ruta Mehta, and Vijay V. Vazirani. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), 525--534, 2014. ACM.
  • 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.
  • 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.
  • Exchange Markets: Strategy meets Supply-Awareness. Ruta Mehta, and Milind Sohoni. In Proceedings of the 9th International Conference on Web and Internet Economics (WINE), 361--362, 2013. Springer.
  • A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities. Jugal Garg, Ruta Mehta, Milind Sohoni and Vijay V. Vazirani. In Proceedings of the 44th annual ACM symposium on Theory of computing (STOC), 525--534, 2012. ACM.
  • 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.
  • 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.
  • Rank-1 Bimatrix Games: A Homeomorphism and a Polynomial Time Algorithm. Bharat Adsul, Jugal Garg, Ruta Mehta, and Milind Sohoni. In Proceedings of the 43rd annual ACM symposium on Theory of computing (STOC), 195--204, 2011. ACM.
  • 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.
  • Nash Equilibria in Fisher Market. Bharat Adsul, Ch. Sobhan Babu, Jugal Garg, Ruta Mehta, and Milind Sohoni. In Proceedings of the 3rd International Symposium on Algorithmic Game Theory (SAGT), 30-41, 2010. Springer.
  • A Simplex-like Algorithm for Fisher Markets. Bharat Adsul, Ch. Sobhan Babu, Jugal Garg, Ruta Mehta, and Milind Sohoni. In Proceedings of the 3rd International Symposium on Algorithmic Game Theory (SAGT), 18{29, 2010. Springer.

Pending Articles

  • Eliciting Binary Performance Metrics. Gaurush Hiranandani, Shant Boodaghians, Ruta Mehta, and Oluwasanmi Koyejo. 2018.
  • End of Potential Line. John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani. 2018.
  • Smoothed Efficient Algorithms and Reductions for Network Coordination Games. Shant Boodaghians, Rucha Kulkarni, and Ruta Mehta. 2018.

Honors

  • Outstanding Post-Doctoral Researcher Award 2014, College of Computing, Georgia Tech. (2013)
  • 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)