Institute
General information about the institute, such as our mission statement, organizational structure, staff directory, history, directions, etc.

See More
Research
Scientific profile with all research groups, topics, collaborations, as well as columns on research at the institute.

See More
News
News and press releases about the institute, as well as a media archive.

See More
- News Overview
- Press Releases
Events
Overview of all events around the institute, such as talks, seminars, lectures, workshops, conferences and public events.

See More
Publications
Overview of all scientific publications of the institute, as well as our preprint and software repositories.

See More
Career
Information on open positions at the institute, benefits of working with us, graduate school, and postdoctoral supervision.

See More

Events
Workshop on Complexity and Information Theory

MPI für Mathematik in den Naturwissenschaften Leipzig

A3 01 (Sophus-Lie room)

conference

12/10/2007 14/10/2007

Workshop on Complexity and Information Theory

- Program
- Scientific Organizers

Program

16:30 - 17:30	Bastian Steudel (MPI MiS, Leipzig) Quantum broadcasting problem in low-power signal processing We assume that discussions on fundamental bounds in classical low-power computing require a quantum theoretical description and that further some kind of synchronization through a 'timing signal' is needed during the computation process. More explicitly, since any closed quantum system with non-trivial evolution contains some information about the time at which it has been initialized, it can be viewed as a 'quantum clock'. We quantify the timing information that it contains using Holevo-Information and discuss limitations that occur if one wants to broadcast this information as well as thermodynamic implications of these limitations. Mainly this is work by Dominik Janzing to which I contributed through my master thesis.
17:30 - 18:00	Coffee & Tea
18:00 - 19:00	Thomas Kahle (MPI MiS, Leipzig) Exponential families and linear codes In this talk we establish a connection between exponential families of k-interactions, 0/1 polytopes and linear codes. We will see how we can map exponential families in a "face"-preserving way, and study a nice convex polytope instead of the closure of a twisted exponential family. Furthermore the coordinates of vertices of this polytopes turn out to form a so called linear code, which is a subspace of the finite vector space $(F_2)^N$.
19:30 - 20:30	Dinner (à la carte and on the basis of individual payment)

09:30 - 11:00	Tyll Krüger (Universität Bielefeld) Konstruktion universeller typischer Mengen: mehrdimensionaler LZ
11:00 - 12:00	Guido Montúfar (TU Berlin) Quanten-Sanov-Theorem im mehrdimensionalen Fall $\bf{Q-Sanov in $ d \geq 2$}$ Um das Resultat ${\em Quanten-Sanov-Theorem}\;$ [Bjelakovic et. al. 2007] auf mehrdimensionale Gittersysteme zu erweitern, wird ein analoger Beweis vorgeschlagen. Die dort eingeführte HP-Bedingung ist im mehrdimensionalen Fall auch equivalent zum Quanten-Sanov-Theorem. Um dieses zu zeigen muss insbesondere die Existenz von universelltypischen Projektoren in dem mehrdimensionalen Fall gezeigt werden.
12:00 - 14:00	Coffee & Tea
14:00 - 15:00	Sascha Delitzscher (TU Berlin) Komplexität und Entropie Ein zentrales Ergebnis der Komplexitätstheorie ist ein Theorem, das von A.A. Brudno 1983 zuerst bewiesen wurde. Es besagt, dass die Entropierate eines ergodischen Prozesses fast sicher gleich der Kolmogorov Komplexität pro Symbol seiner Trajektorien ist. Betrachtet man einen aus zwei Systemen zusammengesetzten ergodischen Prozess, so lässt sich diese Aussage auf die zugehörigen bedingten Größen erweitern. Der Vortrag stellt die beiden Theoreme vor und zeigt Wege auf, diese zu verallgemeinern: Es wird eine leicht modifizierte Version der bedingten Kolmogorov Komplexität vorgestellt. Bei dieser hat die unterliegende Rechenmaschine die Möglichkeit aus einer gegebenen Menge von Daten die zur Berechnung eines Objektes passendsten auszuwählen. Desweiteren wird der Begriff der Komplexität eines klassischen Ensembles, d.h. eines klassischen physikalischen Systems in einer unbekannten Konfiguration, eingeführt. Dabei wird eine Variante, Ensembles als Ausgaben von Turing Maschinen zu 'berechnen', diskutiert und eine Formel zur Berechnung der Komplexität angegeben.
15:00 - 16:00	Tyll Krüger (Universität Bielefeld) Komplexität von Graphen
16:00 - 16:30	Coffee & Tea
16:30 - 17:30	Ruedi Seiler (TU Berlin) Equiquantisierung von Signalen Die Quantisierung von Signalen hat eine weit ber 100 Jahre alte Geschichte. Eine vollstndige Herleitung der zentralen Formel gelang erst krzlich. Sie stammt von Volker Bach.
17:30 - 18:30	Arleta Szkoła (MPI MiS Leipzig) Asymptotic error rates in quantum hypothesis testing We give an overview of some recent results in quantum hypothesis testing mostly presented in [1]. Using both a new trace inequality for pairs of density operators due to Audenaert et al. [2] and a special mapping from pairs of density operators to pairs of probability distributions [3] we derive quantum extensions of the Chernoff distance and the Hoeffding bound. As a byproduct we demonstrate how one part of the quantum Stein's Lemma -the achievability of the quantum relative entropy as the best rate of the probability of error of the type-II- arises from these quantities. Moreover, we discuss the properties of the quantum Chernoff distance as a distance measure on the quantum state space of finite-dimensional complex Hilbert spaces. [1] K.M.R. Audenaert, M. Nussbaum, A. Szkola, F. Verstraete, "Asymptotic Error Rates in Quantum Hypothesis Testing", Preprint No. 84/2007, MPI MiS Leipzig[2] K.M.R. Audenaert, J. Calsamiglia, R. Munoz-Tapia, E. bagan, Li. masanes, A. Acin and F. Verstraete, " Discriminating States: The Quantum Chernoff Bound" , quant-ph/0607216[3] M. Nussbaum, A. Szkola, "The Chernoff lower bound in quantum hypothesis testing", Preprint No. 69/2006, MPI MiS Leipzig

09:00 - 12:00

Internal meeting of the DFG project members

Scientific Organizers

Nihat Ay

Max Planck Institute for Mathematics in the Sciences

Arleta Szkoła

Max-Planck-Institut für Mathematik in den Naturwissenschaften

Workshop on Complexity and Information Theory

Program

Scientific Organizers

Nihat Ay

Arleta Szko&#322;a

Arleta Szkoła