Informatics Seminar (Perspective in Informatics 4B) 2010 - 2011
December 24 (Fri), 16:30 - 18:00
- Place:
Lecture Hall 1, Faculty of Engineering Bldg. No.10, Main Campus
- Title:
On Convex Complexity Measures
- Speaker:
Alexander S. Kulikov (Steklov Institute of Mathematics at St. Petersburg)
- Abstract:
We will consider the problem of proving lower bounds on the size of De
Morgan formulas for Boolean functions. Though easy counting shows that
almost all Boolean functions can be computed only by formulas of
exponential size, we still do not know an explicit function requiring
formulas of size larger than n^3. In the talk, after all the necessary
definitions, we will give an overview of known techniques for proving
lower bounds and then show why many of them fail to prove stronger
than n^2 lower bounds.
Kyoto University
> Graduate School of Informatics
> International Courses
> Informatics Seminar