Menu:

Publications

Submitted / Manuscript
Pricing commodities, or How to sell when buyers have restricted valuations.
Robert Krauthgamer, Aranyak Mehta, Atri Rudra.
Greedy List Intersection.
Robert Krauthgamer, Aranyak Mehta, Atri Rudra, Vijayshankar Raman.
2008
Online Budgeted Matching in Random Input Models with applications to Adwords.
Gagan Goel, Aranyak Mehta.
2007
Adwords Auctions with Decreasing Bid Valuations.
Gagan Goel, Aranyak Mehta.
Progress in Approximate Nash equilibrium.
Constantinos Daskalakis, Aranyak Mehta, Christos Papadimitriou.
To Appear at the 8th ACM Conference on Electronic Commerce (EC): ACM 2007.
Beyond Moulin Mechanisms.
Aranyak Mehta, Tim Roughgarden, Mukund Sundararajan.
To Appear at the 8th ACM Conference on Electronic Commerce (EC): ACM 2007.
Approval Voting: Approximation Algorithms and Heuristics for the Minimax Solution.
R. Legrand, E. Markakis, A. Mehta.
Preliminary version to appear as a 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).
2006
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.
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.
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.
2005
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.
Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions.
Subhash Khot, Richard Lipton, Evangelos Markakis, Aranyak Mehta.
In Proceedings of the first International Workshop on Internet and Network Economics (WINE), Lecture Notes in Computer Science 3828: 92-101, Springer 2005. Invited and accepted to special issue of Algorithmica.
An Auction-Based Market Equilibrium Algorithm for a Production Model.
Sanjiv Kapoor, Aranyak Mehta, Vijay Vazirani.
In Proceedings of the first International Workshop on Internet and Network Economics (WINE), Lecture Notes in Computer Science 3828: 102-111, Springer 2005. Invited and accepted to special issue of Theoretical Computer Science.
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.
Fairness in Congestion Games.
Deeparnab Chakrabarty, Aranyak Mehta, Viswanath Nagarajan, Vijay Vazirani.
Proceedings 6th ACM Conference on Electronic Commerce (EC): 52-57, ACM 2005
On the Fourier coefficients of Symmetric Boolean Functions.
M. Kolountzakis, R. Lipton, E. Markakis, A. Mehta, N. Vishnoi.
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.
2004
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.
2003
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.
Profit-Maximizing Multicast Pricing by Approximating Fixed Points.
Aranyak Mehta, Scott Shenker, Vijay Vazirani.
In Proceedings of the 4th ACM Conference on Electronic Commerce (EC):218-219, ACM 2003. Final version in Journal of Algorithms 58(2): 150-164, February 2006.
Randomized Time Space Tradeoffs for Directed Graph Connectivity.
Parikshit Gopalan, Richard Lipton, Aranyak Mehta.
Proceedings of the 23th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Lecture Notes in Computer Science 2914: 208-216, Springer 2003.
2002
Caching with Expiration Times for Internet Applications.
Parikshit Gopalan, Howard Karloff, Aranyak Mehta, Milena Mihail, Nisheeth Vishnoi.
In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA): 540-547, ACM/SIAM 2002. Final version in Internet Mathematics Vol 2, No. 2: 165-184 2005-2006.
2000
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.