Theory

Changes

CATS-Apr-11-2014 (view source)

Revision as of 14:15, 3 April 2014

5 bytes added ,  14:15, 3 April 2014
→‎Speaker
Line 1: Line 1:  
== Title ==
 
== Title ==
−
The Theory of Equilibrium Computation Has Come Of Age
+
Greedy-like algorithms and a myopic model for the non-monotone submodular maximization problem
    
== Speaker ==
 
== Speaker ==
−
Vijay Vazirani got his Bachelor’s degree in Computer Science from MIT in 1979 and his Ph.D. from the University  
+
Allan Borodin received his BSC from Rutgers University in 1963,
−
of California at Berkeley in 1983. His research career has been centered around the design of algorithms and  
+
and obtained an MSC degree in 1966 from Stevens Institute of Technology
−
computational complexity theory. He has made seminal contributions to the classical maximum matching problem,  
+
while working as a Member of the Technical Staff at Bell Laboratories.
−
approximation algorithms and the computability of equilibria, particularly algorithms for computing market equilibria.
+
He returned full time to graduate school at Cornell in 1966
−
His work in complexity theory includes the Valiant-Vazirani theorem, proving that if UNIQUE-SAT is in P then NP = RP.
+
and received his PhD in 1969. He came to Canada and the University of
−
 
+
Toronto in 1969 for a year or two but forgot to leave. He has been
−
In 2001 he published what was widely regarded as the definitive book on Approximation Algorithms. This book has
+
on the faculty of the Department of Computer Science at Toronto since 1969
−
been translated into Japanese, Polish, French and Chinese.  He was a Distinguished SISL Visitor at the Social and
+
and served as department chair from 1980-1985. He has held
−
Information Sciences Laboratory at Caltech during 2011-12. He is a Guggenheim Fellow and an ACM Fellow.
+
visiting positions at Cornell, ETH Zurich, Universite' de Nice,
 +
Hebrew University, Weizmann University, Technion, Tel Aviv University,
 +
University of Washington
 +
and the Institute for Advanced Study. Professor Borodin is
 +
a fellow of the Royal Society of Canada and a recipient of the
 +
2008 CRM-Fields-PIMS Prize. He was appointed a University Professor
 +
in 2011.
    
== Abstract ==
 
== Abstract ==
−
Profound insights, obtained over the last decade, have elevated equilibrium computation to a
+
We are generally interested in the following not-well defined problem: What
−
full-fledged area within the theory of algorithms and computational complexity. It has its own
+
is a conceptually simple algorithm and what is the power and limitations
−
character which is quite distinct from the computability of optimization problems.
+
of such algorithms? In particular, what is a greedy algorithm
 +
or more generally a myopic algorithm for a combinatorial optimization
 +
problem? And to be even more specific,
 +
motivated by the Buchbinder et al ``online greedy algorithm'' for the
 +
unconstrained non-monotone
 +
submodular maximization problem, what are (if any) the limitations of
 +
algorithms "of this genre" for the general unconstrained problem and for
 +
specific instances of the problem, such as Max-Di-Cut?
   −
Using the powerful notions of complementarity and complementary pivot algorithms, traditional
+
Joint work with Norman Huang
−
complexity classes NP, co-NP, ETR (Existential Theory of Reals) and UTR (Universal Theory of Reals),
  −
and new classes PPAD and FIXP, we will provide a broad overview of this theory as it stands today.
  −
The picture is intensely beautiful! The area still has low-hanging fruit -- we will indicate where
 
Retrieved from "https://wiki.cs.umd.edu/theory/view/Special:MobileDiff/1830...1845"