Changes

2,385 bytes removed ,  22:32, 24 June 2016
no edit summary
Line 1: Line 1:  
='''Algorithms and Theory Group'''=  
 
='''Algorithms and Theory Group'''=  
'''Department of Computer Science[http://www.cs.umd.edu/], University of Maryland, College Park[http://www.umd.edu/]'''.
+
'''[http://www.cs.umd.edu/ Department of Computer Science], [http://www.umd.edu/ University of Maryland, College Park]'''.
    
<br>
 
<br>
Welcome to the Wiki for our group!
+
Welcome to the Wiki for our group! You also follow us on Twitter [https://twitter.com/theorycsumd @theorycsumd ]
    
Theoretical Computer Science (TCS), broadly speaking, is concerned with understanding the very nature of computation:
 
Theoretical Computer Science (TCS), broadly speaking, is concerned with understanding the very nature of computation:
Line 30: Line 30:  
<li> '''Algorithmic Game Theory''':
 
<li> '''Algorithmic Game Theory''':
 
[http://www.cs.umd.edu/~hajiagha/ Mohammad Hajiaghayi],
 
[http://www.cs.umd.edu/~hajiagha/ Mohammad Hajiaghayi],
[http://www.cs.umd.edu/~srin/ Aravind Srinivasan],
+
[http://www.cs.umd.edu/~srin/ Aravind Srinivasan]
 
<br>
 
<br>
 
Mechanism Design in particular Algorithmic Game Theory, which can be viewed as "incentive-aware algorithm design", has become an increasingly important part of (theoretical) computer science in recent years. Recent results show a strong relation between computer science (esp. networking) and economics (esp. game theory), and techniques from each seem well-poised to help with key problems of the other.  Our main goal in this area is to study these connections which produce powerful mechanisms for adaptive and networked environments and several other applied areas, and improve the experience of users of the Web and the Internet. To this end, we do research in several topics such as algorithmic mechanism design; auctions (efficient, revenue-maximizing, sponsored search, etc.); congestion and potential games; cost sharing; existence, computation, and learning of equilibria; game theory in the Internet; network games; price of anarchy; selfish routing, etc.
 
Mechanism Design in particular Algorithmic Game Theory, which can be viewed as "incentive-aware algorithm design", has become an increasingly important part of (theoretical) computer science in recent years. Recent results show a strong relation between computer science (esp. networking) and economics (esp. game theory), and techniques from each seem well-poised to help with key problems of the other.  Our main goal in this area is to study these connections which produce powerful mechanisms for adaptive and networked environments and several other applied areas, and improve the experience of users of the Web and the Internet. To this end, we do research in several topics such as algorithmic mechanism design; auctions (efficient, revenue-maximizing, sponsored search, etc.); congestion and potential games; cost sharing; existence, computation, and learning of equilibria; game theory in the Internet; network games; price of anarchy; selfish routing, etc.
Line 45: Line 45:  
<br><br>
 
<br><br>
 
<li>'''Bioinformatics and Computational Biology''':
 
<li>'''Bioinformatics and Computational Biology''':
[http://www.cbcb.umd.edu/~carlk/ Carl Kingsford],
   
[http://www.cbcb.umd.edu/~mpop Mihai Pop]
 
[http://www.cbcb.umd.edu/~mpop Mihai Pop]
 
<br>
 
<br>
Line 102: Line 101:  
<br>
 
<br>
 
Strings of characters (or bits) is an elementary form for representing information. Pattern matching problems on strings have provided a fertile ground for idea-driven algorithmic research.
 
Strings of characters (or bits) is an elementary form for representing information. Pattern matching problems on strings have provided a fertile ground for idea-driven algorithmic research.
 +
 +
<br><br>
 +
<li> '''Quantum Algorithms''':
 +
[http://www.cs.umd.edu/~amchilds/ Andrew Childs]
 +
<br>
 +
A quantum mechanical representation of information allows one to efficiently perform certain tasks that are intractable within a classical framework.Some of the main topics of research include quantum walk, quantum simulation, quantum algorithms for algebraic problems, and quantum query complexity.
 +
    
<br><br>
 
<br><br>
Line 115: Line 121:  
can be useful in computation.
 
can be useful in computation.
   −
  −
  −
</ul>
  −
  −
  −
== '''''Best Paper Awards''''': ==
  −
  −
<ul>
  −
  −
<li>'''Improved Distributed Algorithms for Coloring and Network Decomposition Problems'''<br>
  −
Aravind Srinivasan<br>
  −
Best student Paper Award in STOC 1992
  −
  −
<br><br>
  −
<li>'''Algorithms for Data Migration with Cloning'''<br>
  −
Samir Khuller, Yoo Ah Kim and Justin Wan<br>
  −
Best Newcomer Award Paper in PODS 2003
  −
  −
<br><br>
  −
<li>'''Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction'''<br>
  −
MohammadTaghi Hajiaghayi (joint work with Erik D. Demaine and Kenichi Kawarabayashi)<br>
  −
Best Paper Award in ISAAC 2006
  −
  −
<br><br>
  −
<li>'''Distributed Ranked Search'''<br>
  −
Bobby Bhattacharjee and Pete Keleher and Aravind Srinivsan (joint work with Vijay Goplakrishnan and Ruggero Morselli)<br>
  −
Best Paper Award in Annual International Conference on High Performance Computing (HiPC) 2007
  −
  −
<br><br>
  −
<li>'''Adaptive Local Ratio'''<br>
  −
Julian Mestre<br>
  −
Best Student Paper Award in SODA 2008
  −
  −
  −
<br><br>
  −
<li>'''TrInc: Small Trusted Hardware for Large Distributed Systems'''<br>
  −
Dave Levin (joint work with John R. Douceur, Jacob R. Lorch and Thomas Moscibroda)<br>
  −
Best Paper Award in USENIX Symposium on Networked Systems Design and Implementation (NSDI) 2009
  −
  −
<br><br>
  −
<li>'''n Analysis of Troubled Assets Reverse Auction'''<br>
  −
Saeed Alaei and Azaraksh Malekian<br>
  −
Best Student Paper Award in WINE 2009
  −
  −
  −
<br><br>
  −
<li>'''A Unified Approach to Ranking in Probabilistic Databases'''<br>
  −
Jian Li, Barna Saha and Amol Deshpande<br>
  −
Best Paper Award in VLDB 2009
  −
  −
  −
<br><br>
  −
<li>'''Codes in Permutations and Error Correction for Rank Modulation'''<br>
  −
Arya Mazumdar and Alexander Barg<br>
  −
Best Student Paper AWard in ISIT 2010
  −
  −
  −
<br><br>
  −
<li>'''Basic Network Creation Games'''<br>
  −
MohammadTaghi Hajiaghayi (joint work with Noga Alon, Erik D. Demaine and Tom Leighton)<br>
  −
Best Paper Award in SPAA 2010
  −
  −
  −
<br><br>
  −
<li>'''When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings'''<br>
  −
Jian Li and Julian Mestre (joint work with Nikhil Bansal, Anupam Gupta, Vishwanathan Nagarajan and Atri Rudra)<br>
  −
Best Paper Award in ESA 2010
  −
  −
  −
<br><br>
  −
<li>'''Predicting Trust and Distrust in Social Networks'''<br>
  −
Tom DuBois, Jennifer Golbeck and Aravind Srinivasan<br>
  −
Best Paper Award in IEEE International Conference on Social Computing (SocialCom) 2011
  −
  −
  −
<br><br>
  −
<li>'''Examining the Evolution of Ties in Social Networks: A Longitudinal Multi-Method Study'''<br>
  −
Tom DuBois and Aravind Srinivasan (joint work with Sridevi Shivarajan)<br>
  −
Adjudged one of the Best Papers at Proc. Academy of Management Annual Meeting, 2012. (Appeared in Best Paper Proceedings)
  −
  −
<br><br>
  −
<li>'''List H-Coloring a Graph By Removing Few Vertices'''<br>
  −
Rajesh Chitnis (joint work with Laszlo Egri and Daniel Marx)<br>
  −
Best Paper AWard in ESA 2013
         
</ul>
 
</ul>
editor
178

edits