This week, which is the last week of presentations, we will have two talks, both on Wednesday. At 11:00, Pekeris, Bharatram will talk about Constructing small-bias sets from algebraic-geometric codes by Avraham Ben-Aroya and Amnon Ta-Shma. At 14:00, Pekeris, Anat will give a talk on derandomization and circuit lower bounds, following parts of chapter 20 in AB book and the beautiful paper of Russell Impagliazzo and Valentine Kabanets Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds.

Advertisement

This Thursday we will have two interesting talks. Yoav will talk about hardness amplification (following chapter 19 of AB-book). This is a classic result everyone should know! The talk will start at 10:00, Pekeris.

At 11:30, faculty room, Ron will present the construction of Bourgain for two-source extractor. This is a beautiful result that everyone should want to know 🙂

This post will be updated with room numbers by tomorrow.

New time slots were allocated this Thursday (and not on Wednesday as announced by mistake yesterday) and on Monday-Wednesday next week. These are the last time slots that I will allocate. Of course, if someone has a problem with these slots we would find a solution.

This week we will have 5 presentations. One on Monday and four on Wednesday. Tomorrow Tom will talk about the paper Derandomized Constructions of k-Wise (Almost) Independent Permutations by Eyal Kaplan, Moni Naor and Omer Reingold. The talk will start at 10:00, Pekeris.

On Wednesday Shani will present A probabilistic-time hierarchy theorem for “slightly non-uniform” algorithm by Boaz Barak. The talk will start at 10:00, Room 261. At 11:30, faculty room, Yinon will present Algorithmic Extensions of Cheeger’s Inequality to Higher Eigenvalues and Partitions by Anand Louis, Prasad Raghavendra, Prasad Tetali and Santosh Vempala.

Later that day, at 15:00 in Room 261, Itay will present the paper An Elementary Construction of Constant-Degree Expanders by Noga Alon, Oded Schwartz, Asaf Shapira. The last talk of the day is by Roee who will talk about Multi-way spectral partitioning and higher-order Cheeger inequalities by James R. Lee, Shayan Oveis Gharan and Luca Trevisan. Roee’s talk will begin at 16:15, room 261.

Note that at 13:30 Igor will give the last talk of the ciruit lower bounds reading group!

Next week however we will have 5 presentations!

This week we will have a single presentation. Tal will talk about an important result by Venkatesan Guruswami, Chris Umans and Salil Vadhan, Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. The presentation will start at Thursday 10:30 in Pekeris.

There are many open slots in the next three weeks and many of you still haven’t chose one. Please try to do so in advance. Thanks!

I’m sorry for the late notice.

A number of open slots have been added in the week of the 15th and the 22nd. Once you choose a slot, please don’t forget to mail me, reserve a room and update the calendar with the room’s name. Also note that Shani’s lecture next Sunday is canceled.

This week we have 4 presentations. On Monday, Avishay will present Reingold’s celebrated result on undirected s-t connectivity in log-space. The presentation will start at 10:30 in Pekeris. Later on that day, Ilan will present the BIW paper – a beautiful construction of a multisource extractor based on additive combinatorics. This lecture will start at 13:30 in room 1.

On Tuesday, Guy will present the paper of Goldreich, in a world of P=BPP. The presentation will start at 10:30 in room 261. Later on Uri will present Viola’s result about fooling low degree polynomials. This will start at 11:45 in the same room.

Shabat Shalom

Tomorrow Eylon will open the presentations season. Eylon will present the paper of Zeev Dvir, Swastik Kopparty, Shubhangi Saraf and Madhu Sudan: Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers, starting at 15:00 in room 141. You are all welcome!

In general, please try to schedule your preferred time slot sooner rather than later so I could adjust accordingly. Also, don’t forget to reserve a room ahead of time.