You are cordially invited to our next Monday Lecture &
Colloquium on July 9th at 14:15 h & 16:00 h at TU Berlin. Location: Technische Universität Berlin Straße des 17. Juni 136 10623 Berlin Time: Monday, July 9th - 14:15 h Lecture: Jeroen Zuiddam (CWI, Amsterdam) Title: Asymptotic spectra of tensors and graphs: matrix
multiplication exponent and Shannon capacity Matrix rank is well-known to be multiplicative under the Kronecker product, additive under the direct sum, normalised on identity matrices and non-increasing under multiplying from the left and from the right by any matrices. In fact, matrix rank is the only real matrix parameter with these four properties. In 1986 Strassen proposed to study the extension to tensors: find all maps from k-tensors to the reals that are multiplicative under the tensor Kronecker product, additive under the direct sum, normalized on diagonal tensors, and non-increasing under acting with linear maps on the k tensor factors. Strassen called the collection of these maps the "asymptotic spectrum of k-tensors". Strassen proved that understanding the asymptotic spectrum implies understanding the asymptotic relations among tensors, including the asymptotic rank. In particular, knowing the asymptotic spectrum means knowing the arithmetic complexity of matrix multiplication, a central problem in algebraic complexity theory.I will give an overview of known elements in the asymptotic spectrum of tensors, including our recent construction which is based on information theory and moment polytopes. This recent construction is joint work with Matthias Christandl and Peter Vrana.Then I will introduce the analogous object in graph theory: the asymptotic spectrum of graphs. I will explain the relation to Shannon capacity and give an overview of known elements in the asymptotic spectrum of graphs. Coffee & Tea Break : Room MA 316 - Third Floor Time: Monday, July 9th - 16:00 h Colloquium: Aaron Williams (Bard College at Simon's
Rock, USA) Title: Fun and Games: The Computational Complexity of
Puzzles and Video Games Most computer
scientists and discrete mathematicians are familiar with
computational complexity due to the famous P = NP conjecture. Some
researchers have a more thorough understanding of the classes P,
NP, and PSPACE since problems in logic, graph theory, and
combinatorial optimization are often classified by their
relationship to one of these classes. More recently, these
concepts have found a wider audience through their application to
puzzles and games. For example, it is known that the number puzzle
Sudoku is NP-complete, whereas the box pushing game Sokoban is
PSPACE-complete. In this talk we establish the computational
complexity of several puzzles and games. We prove that two new
paper and pencil puzzles are NP-complete. These puzzles are called
Pencils and Sto-Stone, and were created by the Japanese publisher
Nikoli that popularized Sudoku. We then prove that several puzzles
that have been implemented as video games are PSPACE-complete.
These games include a row shifting puzzle called MazezaM, a
turnstile puzzle for the Nintendo Game Boy called Kwirk, and a
puzzle called Switches that was invented by undergraduate student
Jonathan Gabor while he was attending high school. Our reductions
use conventional approaches such as Boolean Satisfiability, as
well as some less conventional tools including Gray Codes, and the
new Constraint Logic model pioneered by Hearn and Demaine in their
influential textbook "Games, Puzzles, and Computation". The talk
aims to be accessible to a wide audience, and hopes to encourage
researchers to seek similar results for problems (or puzzles!)
that are close to them. Most of the new results consist of joint
work with undergraduate students at Bard College at Simon's Rock.
-- Graduiertenkolleg 'Facets of Complexity' www.facetsofcomplexity.de/monday |