Changes

='''Algorithms and Theory Group'''=

Welcome to the Wiki for the Algorithms and Theory Group at University of Maryland.

'''[http://www.cs.umd.edu/ Department of Computer Science], [http://www.umd.edu/ University of Maryland, College Park]'''.

<br>

<br>

We start with an applicable dictionary definition of ``theory'': The general or abstract principles of a science, or an art, or

Welcome to the Wiki for our group! You also follow us on Twitter [https://twitter.com/theorycsumd @theorycsumd ]

a body of theorems presenting a concise systematic view of a subject.  

Research in Theory of Computation includes three parts. <BR>

 

What problems can be solved by computers? And how efficiently can such problems be solved? Can `hard' problems be used to our advantage in any way? TCS encompasses research in such diverse areas as complexity theory, algorithms, cryptography, distributed computing, machine learning, and more; the common thread is a focus on precise models and rigorous mathematical analysis of particular problems within those models.

We have a strong group of faculty actively working in this area. We also have a large number of students who are encouraged to get involved early by attending weekly TCS reading groups run by the group. Brief descriptions of faculty research interests follow.

  Abstract salient features of a computational task; the outcome of abstraction  is usually a mathematical model.

  Use analytical tools to study various issues within the model.

  Go back and relate the contributions of studies within the model to the motivating computational task.

<ul>

<ul>

<li> Applied Algorithmics:

<li> '''Applied Algorithmics''':

[http://www.umiacs.umd.edu/~joseph/ Joseph Ja'Ja'],

[http://www.umiacs.umd.edu/~joseph/ Joseph Ja'Ja'],

[http://www.cs.umd.edu/~hajiagha/ Mohammad Hajiaghayi],

[http://www.cs.umd.edu/~hajiagha/ Mohammad Hajiaghayi],

<br><br>

<br><br>

<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.

<br><br>

<br><br>

<li> Approximation Algorithms:

<li> '''Approximation Algorithms''':

[http://www.cs.umd.edu/~samir Samir Khuller],

[http://www.cs.umd.edu/~samir Samir Khuller],

[http://www.cs.umd.edu/~hajiagha/ Mohammad Hajiaghayi],

[http://www.cs.umd.edu/~hajiagha/ Mohammad Hajiaghayi],

<br><br>

<br><br>

<li>Bioinformatics and Computational Biology:

<li>'''Bioinformatics and Computational Biology''':

[http://www.cbcb.umd.edu/~mpop Mihai Pop]

[http://www.cbcb.umd.edu/~mpop Mihai Pop]

<br>

<br>

Bioinformatics and Computational Biology involve the application of algorithmic theory to solving biological problems, in particular those problems arising from the modern shift of biological research towards high-throughput experimental techniques.  As an example, determining the DNA sequence of organisms could not be possible without sophisticated algorithms used to assemble together the many small fragments generated by sequencing machines.  Computational Biology at University of Maryland is conducted in close collaboration with biologists from the UMD College of Life Sciences and from other institutions.

Bioinformatics and Computational Biology involve the application of algorithmic theory to solving biological problems, in particular those problems arising from the modern shift of biological research towards high-throughput experimental techniques.  As an example, determining the DNA sequence of organisms could not be possible without sophisticated algorithms used to assemble together the many small fragments generated by sequencing machines.  Computational Biology at University of Maryland is conducted in close collaboration with biologists from the life-science departments and from other institutions.

<br><br>

<br><br>

<li> Coding Theory:

<li> '''Coding Theory''':

[http://www.enee.umd.edu/~abarg/ Alexander Barg]

[http://www.enee.umd.edu/~abarg/ Alexander Barg]

<br>

<br>

<br><br>

<br><br>

<li> Complexity Theory:

<li> '''Complexity Theory''':

[http://www.cs.umd.edu/~gasarch/ William Gasarch],

[http://www.cs.umd.edu/~gasarch/ William Gasarch],

[http://www.cs.umd.edu/~jkatz/ Jonathan Katz]

[http://www.cs.umd.edu/~jkatz/ Jonathan Katz]

<br><br>

<br><br>

<li> Computational Geometry:

<li> '''Computational Geometry''':

[http://www.cs.umd.edu/~samir Samir Khuller],

[http://www.cs.umd.edu/~samir Samir Khuller],

[http://www.cs.umd.edu/~mount/ David Mount]

[http://www.cs.umd.edu/~mount/ David Mount]

<br><br>

<br><br>

<li> Cryptography:

<li> '''Cryptography''':

[http://www.cs.umd.edu/~jkatz/ Jonathan Katz],

[http://www.cs.umd.edu/~jkatz/ Jonathan Katz],

[http://www.enee.umd.edu/~abarg/ Alexander Barg]

[http://www.enee.umd.edu/~abarg/ Alexander Barg]

<br><br>

<br><br>

<li> Parallel Algorithms:

<li> '''Fixed-Parameter Algorithms''':

 

 

<li> '''Parallel Algorithms''':

[http://www.cs.umd.edu/~kruskal/ Clyde Kruskal],

[http://www.cs.umd.edu/~kruskal/ Clyde Kruskal],

[http://www.umiacs.umd.edu/~joseph/ Joseph Ja'Ja'],

[http://www.umiacs.umd.edu/~joseph/ Joseph Ja'Ja'],

[http://www.umiacs.umd.edu/~vishkin/ Uzi Vishkin]

[http://www.umiacs.umd.edu/~vishkin/ Uzi Vishkin]

<br>

<br>

Thinking algorithmically in parallel provides an interesting ``alien intellectual culture'', relative to previous algorithmic theories. Current UMD researchers have had a strong presence in this field for over two decades, as evidenced by the recent recognition of 2 parallel algorithms researchers: Clyde Kruskal and Uzi Vishkin, as [http://www.isihighlycited.com Highly Cited Researchers] -- Kruskal and Vishkin are 2 of a total of 15 active UMD faculty members to be recognized by ISI Thompson, publishers of the science citation index. The PRAM-On-Chip project at UMD is a direct outgrowth of our theoretical work. The project offers a concrete agenda for challenging the 1946 von-Neumann architecture, through streamlining the massive knowledge base developed by the parallel algorithms community with the roadmap for CMOS VLSI.

Thinking algorithmically in parallel provides an interesting ``alien intellectual culture", relative to previous algorithmic theories. Current UMD researchers have had a strong presence in this field for over three decades, as evidenced by the recognition of 2 parallel algorithms researchers: Clyde Kruskal and Uzi Vishkin, as [http://www.isihighlycited.com Highly Cited Researchers]. The PRAM-On-Chip project at UMD is a direct outgrowth of our theoretical work. The project offers a concrete agenda for challenging the 1946 von-Neumann architecture, through streamlining the massive knowledge base developed by the parallel algorithms community with the roadmap for CMOS VLSI. Using our hardware and software prototypes, we recently demonstrated parallel speedups that beat all current platforms by orders of magnitude on the most advanced parallel algorithms in the literature, including for max-flow, graph biconnectivity and graph triconnectivity. This stress test validates our 30-year old hypothesis that the PRAM algorithmic theory can save parallel computing from its programming woes, while traversing an architecture narrative that has belittled for decades the PRAM theory, stipulating that it is too simplistic for any existing or future parallel machine. The demonstrated advantage is especially important for the so-called, irregular, fine-grained programs that all commercial platforms to date fail to support effectively.  

<br><br>

<br><br>

<li> Pattern Matching:

<li> '''Pattern Matching''':

[http://www.umiacs.umd.edu/~vishkin/ Uzi Vishkin]

[http://www.umiacs.umd.edu/~vishkin/ Uzi Vishkin]

<br>

<br>

<br><br>

<br><br>

<li> Randomized Algorithms:

<li> '''Quantum Algorithms''':

 

 

<li> '''Randomized Algorithms''':

[http://www.cs.umd.edu/~hajiagha/ Mohammad Hajiaghayi],

[http://www.cs.umd.edu/~hajiagha/ Mohammad Hajiaghayi],

[http://www.cs.umd.edu/~jkatz/ Jonathan Katz],

[http://www.cs.umd.edu/~jkatz/ Jonathan Katz],