



Theory
Afternoon
January
15, 2008


Rm.121,
Ho Sin Hang Engineering Bldg., CUHK

Prof.
Luca Trevisan , Professor of University of Califronia,
Berkeley 
Title
: 
Sublinear Time Algorithms 
Time: 
2:30p.m
 3:15p.m. 
Abstract:

Provided
that one is willing to use randomness and to
tolerate an approximate answer, many computational
problems admit ultrafast algorithms that run
in less than linear time in the length of the
input. In many interesting cases, even algorithms
that run in constant time are known, whose efficiency
depends only on the accuracy of the approximation
and not on the length of the inputs. In this
survey talk we will give an overview of several
such algorithms, with a focus on graph problems.

Biography:

Luca
Trevisan is an associate professor of computer
science at the University of California, Berkeley.
Luca received his Laurea (BSc) degree in 1993
and his Dottorato (PhD) in 1997, both from the
University of Rome La Sapienza. Before coming
to Berkeley in 2000, Luca was a postdoc at
MIT and at DIMACS, and an assistant professor
at Columbia University.
Luca's
research is in theoretical computer science,
and most of his work has been in two areas:
(i) the relation between pseudorandomness, derandomization,
averagecase complexity, coding theory, and
the explicit construction of expanderlike graphs;
and (ii) the theory of probabilistically checkable
proofs and its relation to the approximability
of combinatorial optimization problems.
Luca
received the STOC 1997 student paper award (now
the Danny Lewin award), the 2000 Oberwolfach
Prize, and the 2000 Sloan Fellowship. He lectured
in the 2000 IAS/PCMI Summer School on Computational
Complexity and he was an invited speaker at
the 2006 International Congress of Mathematicians
in Madrid.



Dr.
Andrej Bogdanov, Tsinghua University 
Title
: 
Averagecase hardness for errorless heuristics 
Time: 
3:20p.m
 4:05p.m. 
Abstract:

We
say a problem is tractable on average if it
can be solved on a "good" fraction of instances
by an efficient algorithm. To make this definition
precise, we need to make two choices: First,
what is a "good" fraction of instances; and
second, what should the algorithm do when it
fails to solve the problem?
For
heuristic algorithms for NP  these are allowed
to behave arbitrarily on instances where they
fail to solve the problem  it is known that
the definition is robust with respect to the
fraction of instances. Namely, if all problems
in NP can be solved on a 51% fraction of instances
by heuristic algorithms, then all problems in
NP can be solved on almost all instances by
heuristic algorithms.
We
consider the analogous question for errorless
heuristics  these algorithms must output "I
don't know" on instances where they fail to
solve the problem  and show that if all problems
in NP can be solved on a (say) 1% fraction instances
by errorless heuristics, then all problems in
NP can be solved on almost all instances by
errorless heuristics. (This is based on joint
work with Muli Safra.) 
Biography:

Andrej
Bogdanov is a postdoctoral researcher at ITCS
at Tsinghua University. He received his B. Sc.
in mathematics from MIT in 2000, his M. Eng.
in electrical engineering and computer science
from MIT in 2001, and his Ph. D. in computer
science from UC Berkeley in 2005. Before coming
to Tsinghua he was a postdoc at the Institute
for Advanced Study in Princeton and the DIMACS
center at Rutgers University. Andrej's research
interests are in computational complexity, including
pseudorandomness, averagecase complexity, and
arithmetic complexity. 


Panel
Discussion

Time: 
4:15p.m
 5:00p.m. 




