Mathematics, Physics & Computer Science Seminar Series

October 26, 2022 from 4:30 PM at Governor's Palace, Moravské náměstí 1a, Baroque Hall

Irit Dinur

Expanders in higher dimensions

Abstract:

Expander graphs have been studied in many areas of mathematics and in computer science with versatile applications, including coding theory, networking, computational complexity and geometry.

High-dimensional expanders are a generalization that has been studied in recent years and their promise is beginning to bear fruit. In the talk, I will survey some powerful local to global properties of high-dimensional expanders, and describe several interesting applications, ranging from convergence of random walks to construction of locally testable codes that prove the c3 conjecture (namely, codes with constant rate, constant distance, and constant locality).

==================================
The PCP theorem

The PCP theorem says that any mathematical proof can be written in a special "PCP" format such that it can be verified, with arbitrarily high probability, by sampling only a few symbols in the proof. Hence the name, Probabilistically Checkable Proofs (PCPs). Alternatively and equivalently, any system of multivariate polynomial equations can be efficiently converted into another, so that if no input satisfies all equations in the former, no input satisfies even a tiny fraction of the equations in the later. Moreover, each of the new equations will involve only 3 variables.

This theorem is the key to understanding the difficulty of approximation and optimization problems; and also amazingly finds uses in modern cloud computing protocols. We will explain the context and meaning of the theorem, and outline a proof that relies on expander graphs, which are a central combinatorial object in numerous computer science and mathematical areas.

Irit Dinur is interested in theoretical computer science, and especially in error-correcting codes and probabilistically checkable proofs, both of which capture a certain “robustness” in computation. Currently, she is interested in connecting these to so-called high-dimensional expansion​—an analogue of expander graphs that draws on group theory, topology, and combinatorics.

Dear Friends of Hikes and Mathematics,

you are cordially invited to the 38th mathematical hike planned on Saturday, 22nd of October. The official start takes place at the bus stop "Komořany, EDP" at 10:36. We recommend the bus 602 at 9:51 at the "Zvonařka" station.

This hike is a special one as it will be led by our colleague David Kruml through his woods. We leave Komořany following the green path and at "Panská skála" enter the woods. We continue to Viničné Šumice and go back to Brno by bus. The hike is 13 km but crossing the forest cover is more demanding. We strongly recommend proper footwear (for mud, etc.) and protective clothing.

All information and photos can be found at https://conference.math.muni.cz/vylety/index.php?id=kronika. (in CZ)

Looking forward to see you soon!

Pavel Francírek or Jonatan Kolegar, organizers
Jan Slovák, Director of the Department of Mathematics and Statistics

If you have questions, send them to This e-mail address is being protected from spambots. You need JavaScript enabled to view it .

Dear Friends of Hikes and Mathematics,

the 37th mathematical hike is planned on the 13th of August.

Meet near the Maloměřice bridge  (49.2156853N, 16.6422850E) at 06:30h.

Every participant will contribute to determine the path by a dice roll on predetermined crossroads. Thus it will be (not entirely) a random walk all day (possibility to leave anytime), our goal is to walk 40 km.

All information and photos can be found at https://conference.math.muni.cz/vylety/. (in CZ)

Have a great summer,

Pavel Francírek or Jonatan Kolegar, organizers
Jan Slovák, Director of the Department of Mathematics and Statistics

Dear Friends of Hikes and Mathematics,

The 36th mathematical hike is planned on the 21st of May.

We meet at 09:34 at the train station in Dolní Loučky. We recommend going by the train that leaves Brno main train station at 8:53.

We have planned a 16 km hike to Tišnov (train station) through Deblín.

All information and photos can be found at https://conference.math.muni.cz/vylety/. (in CZ)

Looking forward to see you soon and have a wonderful spring season,

Jana Bartoňová and Jonatan Kolegar, organizers
Jan Slovák, Director of the Department of Mathematics and Statistics