Talks - Fall 2017

ArithmeticCircuit

Title

Speaker

Date

Time

Venue

Abstract

Lower Bounds and PIT for Non-Commutative Arithmetic circuits with Restricted Parse Trees

Srikanth Srinivasan, Mathematics, IIT Bombay

25 July, 2017

6pm

KD102

We investigate the power of Non-commutative Arithmetic Circuits, which compute polynomials over the *free* non-commutative polynomial ring F, where variables do not commute. We consider circuits that are restricted in the ways in which they can compute monomials: this can be seen as restricting the families of parse trees that appear in the circuit. Such restrictions capture essentially all non-commutative circuit models for which lower bounds are known. We prove several results about such circuits, including lower bounds that generalize previous results, make progress towards unresolved conjectures, and PIT algorithms.

Joint with Guillaume Lagarde (Univ. Paris Diderot) and Nutan Limaye (CSE Dept. IIT Bombay). To appear in MFCS'17. Paper can be found at https://eccc.weizmann.ac.il/report/2017/077/

ALL SESSIONS


Contact

Image

Sumanta Ghosh

Head Co-ordinator

Image

Rajendra Kumar

Co-ordinator

Image

Mahesh S R

Co-ordinator