[Proof Complexity] Seminar Wed Apr 28 at 15:00 CET with Amir Yehudayoff: Slicing the hypercube is not easy

[Jakob Nordström]

Dear all,

On Wednesday April 28 at 15:00 CET we will have a joint BARC-MIAO seminar with Amir Yehudayoff from Technion -- Israel Institute of Technology titled "Slicing the hypercube is not easy". See below for the abstract.

We will meet virtually at https://lu-se.zoom.us/j/61925271827 . Please feel free to share this information with colleagues who you think might be interested. We are also planning to record the seminar for people who would like to hear the talk but cannot attend.

We will use the default MIAO format, in which seminars consist of two parts: first a 50-55-minute regular talk, and then after a break a ca-1-hour in-depth technical presentation with (hopefully) a lot of interaction. The intention is that the first part of the seminar will give all listeners an overview of some exciting research results, and after the break people who have the time and interest will get an opportunity to really get into the technical details. (However, for those who feel that the first part was enough, it is perfectly fine to just discretely drop out during the break. No questions asked; no excuses needed.)

More information about upcoming MIAO seminars can be found at http://www.csc.kth.se/~jakobn/videoseminars/ (an address that should change soonish, but for now it is what it is). Recordings of some previous seminars are available at https://www.youtube.com/channel/UCN0G2Wfl9-sAKrVLVza7z4A . If you do not wish to receive these announcements, or receive several copies of them, please send a message to jakob.nordstrom at cs.lth.se.

Best regards,
Jakob Nordström

**********

Wednesday Apr 28 at 15:00 CET
Slicing the hypercube is not easy
(Amir Yehudayoff, Technion -- Israel Institute of Technology)

How many hyperplanes are needed to slice all edges of the hypercube? This question has been studied in machine learning, geometry and computational complexity since the 1970s. We shall describe (most of) an argument showing that more than n^{0.57} hyperplanes are needed, for large n. We shall also see a couple of applications. This is joint work with Gal Yehuda.


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +46 70 742 21 98
http://www.csc.kth.se/~jakobn/ (webpages still in transit)