[Facets-of-complexity] Invitation to Monday Lecture & Colloquium - July 9th 2018

[Ita Brunke <i.brunke@inf.fu-berlin.de>]

You are cordially invited to our next Monday Lecture & Colloquium on July 9th at 14:15 h & 16:00 h at TU Berlin.

Location:

Room MA 041 - Ground Floor
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

Abstract:

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

Abstract:

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