11:45 am, Lecture Hall 5
Towards hitting-sets for multilinear depth-3 circuits
Nitin Saxena
IIT Kanpur.
22-05-15

---

Abstract

Recently, the depth-3 circuit model has emerged as a key step in understanding general arithmetic circuits. In this talk we will focus on the (open) question of testing whether a given *multilinear* depth-3 circuit is zero. In particular, we give nontrivial constructions of hitting-sets for a *sum-of-few set-multilinear* depth-3. The main phenomenon here are "low evaluation-dimension" & "low-support rank concentration".

The talk is based on a joint work with Rohit Gurjar, Arpita Korwar & Thomas Thierauf.

Comments: The talk would assume some familiarity with (or interest in) arithmetic circuit complexity. A 60mins board-talk should suffice.