Menu:

Research Publications by Area

Search Engine Adwords Auctions
Computation of Nash Equilibrium
Auctions and Mechanisms
Pricing and Allocations
Learning Theory
Miscellaneous
Seach Engine Adwords Auctions
Adwords and Generalized Online Matching.
Aranyak Mehta, Amin Saberi, Umesh Vazirani, Vijay Vazirani.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS): 264-273, IEEE Computer Society 2005.
See also Sara Robinson's SIAM News article on this.
Adwords Market: An analysis of the greedy online algorithm in distributional models.
Gagan Goel, Aranyak Mehta.
Submitted.
Adwords Auctions with Decreasing Bid Valuations.
Gagan Goel, Aranyak Mehta.
Submitted.
Computation of Nash Equilibrium
Playing Large Games using Simple Strategies.
Richard Lipton, Evangelos Markakis, Aranyak Mehta.
Proceedings of the 4th ACM Conference on Electronic Commerce (EC): 36-41, ACM 2003.
A note on Approximate Nash equilibrium.
Constantinos Daskalakis, Aranyak Mehta, Christos Papadimitriou.
Proceedings of the second International Workshop on Internet and Network Economics (WINE), Lecture Notes in Computer Science 4286: 297-306, Springer 2006.
Progress in Approximate Nash equilibrium.
Constantinos Daskalakis, Aranyak Mehta, Christos Papadimitriou.
To Appear at the 8th ACM Conference on Electronic Commerce (EC): ACM 2007.
Auctions and Mechanisms
Beyond Moulin Mechanisms.
Aranyak Mehta, Tim Roughgarden, Mukund Sundararajan.
To Appear at the 8th ACM Conference on Electronic Commerce (EC): ACM 2007.
A Simple Characterization for Truth-Revealing Single-Item Auctions.
Kamal Jain, Aranyak Mehta, Kunal Talwar, Vijay Vazirani.
Proceedings of the first International Workshop on Internet and Network Economics (WINE), Lecture Notes in Computer Science 3828: 122-128, Springer 2005.
Randomized Truthful Auctions of Digital Goods are Randomizations over Truthful Auctions.
Aranyak Mehta, Vijay Vazirani.
Proceedings of the 5th ACM Conference on Electronic Commerce (EC): 120-124, ACM 2004.
An Auction-Based Market Equilibrium Algorithm for a Production Model.
Sanjiv Kapoor, Aranyak Mehta, Vijay Vazirani.
Invited and accepted to special issue of Theoretical Computer Science. Earlier version in Proceedings of the first International Workshop on Internet and Network Economics (WINE), Lecture Notes in Computer Science 3828: 102-111, Springer 2005.
Pricing and Allocations
Profit-Maximizing Multicast Pricing by Approximating Fixed Points.
Aranyak Mehta, Scott Shenker, Vijay Vazirani.
Journal of Algorithms 58(2): 150-164, February 2006. Earlier version in Proceedings of the 4th ACM Conference on Electronic Commerce (EC): 218-219, ACM 2003.
Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions.
Subhash Khot, Richard Lipton, Evangelos Markakis, Aranyak Mehta.
Invited and accepted to special issue of Algorithmica. Earlier Version in Proceedings of the first International Workshop on Internet and Network Economics (WINE), Lecture Notes in Computer Science 3828: 92-101, Springer 2005.
Fairness in Congestion Games.
Deeparnab Chakrabarty, Aranyak Mehta, Viswanath Nagarajan, Vijay Vazirani.
Proceedings 6th ACM Conference on Electronic Commerce (EC): 52-57, ACM 2005
Pricing commodities, or How to sell when buyers have restricted valuations.
Robert Krauthgamer, Aranyak Mehta, Atri Rudra.
Submitted.
Learning Theory
On the Fourier coefficients of Symmetric Boolean Functions.
M. Kolountzakis, R. Lipton, E. Markakis, A. Mehta, N. Vishnoi.
Submitted. Also appears as: Mihail Kolountzakis, Vangelis Markakis, Aranyak Mehta. Learning Symmetric k-Juntas in time n^{o(k)}, presented at the Workshop on Interface Between Harmonic Analysis and Number Theory, CIRM, Luminy, 2005.
On the Fourier Spectrum of Symmetric Boolean Functions with Applications to Learning Symmetric Juntas.
Richard Lipton, Evangelos Markakis, Aranyak Mehta, Nisheeth Vishnoi.
Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC): 112-119, IEEE Computer Society 2005.
Design is as easy as Optimization
Deeparnab Chakrabarty, Aranyak Mehta, Vijay Vazirani.
Proceedings, Part I, of the 33rd International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science 4051: 477-488, Springer, 2006.
Miscellaneous
Approval Voting: Approximation Algorithms and Heuristics for the Minimax Solution.
R. Legrand, E. Markakis, A. Mehta.
Preliminary version to appear as poster paper in the proceedings of the Sixth International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 07), 3pgs. Preliminary version presented in the 1st International Workshop on Computational Social Choice (COMSOC), 2006. (Full version under submission).
On Earthmover Distance, Metric Labeling, and 0-Extension
Howard Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC): 547-556, ACM 2006.
Caching with Expiration Times for Internet Applications.
Parikshit Gopalan, Howard Karloff, Aranyak Mehta, Milena Mihail, Nisheeth Vishnoi.
Internet Mathematics Vol 2, No. 2: 165-184} 2005-2006. Earlier version in Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA): 540-547, ACM/SIAM 2002.
Keeping Track of the Latest Gossip in Shared Memory Systems.
Bharat Adsul, Aranyak Mehta, Milind Sohoni.
Proceedings of the 23th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Lecture Notes in Computer Science 1974: 477-488, Springer 2000.
Greedy List Intersection.
Robert Krauthgamer, Aranyak Mehta, Atri Rudra, Vijayshankar Raman.
Submitted.