Theory Afternoon

January 15, 2008

 

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

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 ultra-fast 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 post-doc 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, average-case complexity, coding theory, and the explicit construction of expander-like 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.

Title :

Average-case hardness for errorless heuristics

Time:

3:20p.m - 4:05p.m.

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, average-case complexity, and arithmetic complexity.

Time:

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