BIU Theory Seminar begins!

[Talya Eden]

Greetings, all!

Exciting news – the theory seminar kicks off next week, on January 3rd! Join us every Wednesday at 12:00 in the CS building 503, room 328.

We extend a warm invitation to all, and we encourage you to invite your students to join as well. For more information and joining the mailing list and google calendar, please visit: https://theory.cs.biu.ac.il/

Our inaugural speaker is Dor Minzer from MIT with the following talk. See you there, Talya and Arnold

Title: On global hypercontractivity and optimal testing of Reed-Muller codes.

Abstract:

Reed-Muller codes are an important family of error correcting codes that plays a crucial role in a number of results in theoretical computer science. 

The primary topic of this talk is how to establish improved local testability results for Reed-Muller codes via global hypercontractive inequalities, a recent generalization of hypercontractive inequalities. 

For the field of size $q = 2^r$ and degree $d$, it was proved [Bhattacharyya et al., Haramaty et al.] that the corresponding Reed-Muller code is testable with $C_q * q^{2 d/q}/\eps$ queries.

In this talk, we will discuss improvements of this result:

(1) In the case that q is prime we improve the implicit constant $C_q$ (from tower-type bound to a polynomial). 

(2) In the case that q is a prime power, say $q = 2^r$, we manage to improve the query complexity nearly quadratically.

Our proof technique is completely different compared to earlier works and applies to more general settings of code (and not only the Reed-Muller codes), 

such as the case of affine lifted codes and codes that admit sufficiently nice local characterizations and symmetries.

In this talk, we will give a gentle introduction to the concept of global hypercontractivity, and explain the relation of the to the problem of optimal testing of Reed-Muller codes.

Based on joint works with Tali Kaufman and Kai Zheng.

[Arnold Filtser]

The THeory seminar starts now!

The room is 328 in the new CS building/.

--
You received this message because you are subscribed to the Google Groups "BIU Theory Seminar" group.
To unsubscribe from this group and stop receiving emails from it, send an email to biu-theory-semi...@cs.biu.ac.il.
To view this discussion on the web visit https://groups.google.com/a/cs.biu.ac.il/d/msgid/biu-theory-seminar/CAHYGKUwvkVyE%2BTokiWPEWKjeesO%3DC1%3D6zXSYqxCW0z2yw5EBQw%40mail.gmail.com.
For more options, visit https://groups.google.com/a/cs.biu.ac.il/d/optout.