Sergei Artemov, Computer-Aided Proofs and Their Significance
Abstract: Computer-assisted proofs are playing an increasingly visible role in mathematics.
Their scope ranges from routine uses of computational algebra packages to dramatic
new discoveries which make newspaper headlines, such as the four-color problem,
Kepler's conjecture, Robbins' conjecture. Some of these proofs rely heavily upon modules
that compute numerical values or decision procedures which do not necessarily produce certifiable
proofs. In this talk we will discuss some questions concerning these developments.
To what extent can one trust computer-generated proofs? Are computer-generated solutions
more trustworthy than conventional hand-checked proofs? Can computer proofs be `elegant',
or provide insights about the structure of mathematical objects? Do incompleteness phenomena
extend to the foundations of verification? For that matter, can a verifier be verified?
Yuri Gurevich, What's polynomial time anyway?
Abstract: In conventional computational complexity inputs are (or can be adequately represented
by) strings. This is restrictive. Think for example of databases. Modern database query languages do not leak
out implementation dependent details. If the database is a directed graph, you cannot get the first vertex.
Legitimate queries do not distinguish between isomorphic databases. There are other areas of computer science
where the need of more general complexity theory is apparent, for example specification of computer systems. We
will argue that inputs should be structures (in the sense of mathematical logic) and will survey the complexity
theoretic aspects of the theory of computations with structures.
Mark Hillery, Quantum walks and quantum algorithms
Abstract: Quantum walks are quantum versions of random walks. Unlike standard random walks, they
can exhibit interference, in particular the effects of two paths that lead to the same point can cancel rather
than add. This leads to unexpected behavior. For example, they spread faster than classical random walks.
They can also be used to realize some quantum algorithms. In particular, they provide a simple illustration of
the quantum search algorithm and an illustration of the Deutsch-Jozsa algorithm, a procedure that
distinguishes between types of Boolean functions.
Alexander Razborov, Feasible Proofs and Computations
Abstract: The concepts of proof and computation are central to virtually any intellectual human
activity. However, before the remarkable advances of the 20th century mathematical logic, the border between
them had never been sharp even in the context of pure mathematics. It was only in the work of these great
logicians that the separation between proofs and computations became rigorous and (as everybody thought) final.
It should be also mentioned, of course, that the separation on the conceptual level also brought along a
multi-faced and mutually beneficial partnership with results unthinkable of in the pre-Goedel world.
This talk is devoted to a *reverse* trend that results from adding the new element of feasibility (or
efficiency) into this millennial-old brew. Strangely enough, this seemingly innocent addition has led to many
new intriguing facets of the interaction between (slightly compromised versions of) proofs and computations.
And, remarkably, we once again begin seeing more and more creatures with morphing features. We will attempt a
guided (and highly informal!) tour through the areas where these creatures dwell, like Propositional proof
Complexity, NP-Completeness and (time permitting) Interactive and Probabilistically Checkable Proofs. And we
will try to convey, using concrete and intertwined examples, the general feeling of complexity and intricacy of
relations between proofs and computations in this emerging reality.
Avi Wigderson, The power and weakness of randomness in computation
Abstract: Humanity has grappled with the meaning and utility of randomness
for centuries. Research in the Theory of Computation in the last
thirty years has enriched this study considerably. I will talk about
two main aspects of this research on randomness, demonstrating its
power and weakness respectively.
(1) Randomness is paramount to computational efficiency: I will
show how the use of randomness can dramatically speed up computation
(and do other wonders) for a variety of problems and settings.
(2) Computational efficiency is paramount to understanding randomness:
I will explain the new, computationally-motivated definition of
randomness, and try to argue its merits as the "right" definition.
I will then show how such randomness may be generated deterministically,
from computationally difficult problems.