AG 1   Info

AG Audience

English

60 Minutes

Saarbrücken

The first step in almost all lower bound proofs is to find a good starting model to attack the circuit class of interest. This is normally achieved via a "depth reduction" to obtain a "shallow circuit" of not too large size. For most of the lower bounds in depth-4 circuits, this step is provided by the results of [Agrawal-Vinay] and subsequent strengthening by [Koiran] and [Tavenas]. Other lower bounds, such as the recent non-homogeneous depth-three lower bound by [Kayal-Saha] build on a depth reduction to depth three circuits [Gupta et al.].

In this talk, we shall see an overview of some of these depth reduction results and how they directly influenced lower bounds subsequently. We shall also see a slightly different perspective* of [Tavenas] strengthening of [Agrawal-Vinay] that might have some relevance to attacking homogeneous formulas.

Based on joint work with V Vinay

Karteek Sreenivasaiah

--email hidden

passcode not visible

logged in users only