Tata Institute of Fundamental Research
Some Lower Bounds for Depth 2 Circuits with Threshold and Mod Gates
Project Seminar
Speaker:
Tulasi mohan Molli
Organiser:
Prahladh Harsha
Date:
Thursday, 31 Mar 2016, 14:00 to 15:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: In this talk, we will see some lower bound techniques for depth 2 circuits with threshold and mod gates. We focus mainly on two techniques to prove lower bounds for threshold circuits: communication complexity and random restrictions.
The communication complexity approach for proving lower bounds is based on the observation that depth 2 circuits with a threshold gate at the top and a small number of low communication gates at the bottom have efficient randomized protocols. So, one approach for proving lower bounds for the above mentioned classes of circuits is to produce a function which has small discrepancy. The lower bound follows from the well known result that functions with small discrepancy have large randomized communication complexity.
The function with small discrepancy is obtained by lifting a base function with large sign degree by a process called masking. This method of lifting to obtain hard functions was used by Krause and Pudlak to obtain functions with large sign monomial complexity from a base function with large sign degree. This shows an exponential lower bound for depth 2 threshold circuits with AND gates at the bottom. We will see a degree-discrepency which says that if the sign degree of the base function is large, then the discrepancy of it's lift is small.
In our work, we observed that masking the Universal Threshold function which is a linear threshold function also gives rise to a function which has small discrepancy. Thereby, we show that for a lifted function to be hard, the base function need not have high sign degree.
| Speaker: | Tulasi mohan Molli |
| Organiser: | Prahladh Harsha |
| Date: | Thursday, 31 Mar 2016, 14:00 to 15:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: In this talk, we will see some lower bound techniques for depth 2 circuits with threshold and mod gates. We focus mainly on two techniques to prove lower bounds for threshold circuits: communication complexity and random restrictions.
The communication complexity approach for proving lower bounds is based on the observation that depth 2 circuits with a threshold gate at the top and a small number of low communication gates at the bottom have efficient randomized protocols. So, one approach for proving lower bounds for the above mentioned classes of circuits is to produce a function which has small discrepancy. The lower bound follows from the well known result that functions with small discrepancy have large randomized communication complexity.
The function with small discrepancy is obtained by lifting a base function with large sign degree by a process called masking. This method of lifting to obtain hard functions was used by Krause and Pudlak to obtain functions with large sign monomial complexity from a base function with large sign degree. This shows an exponential lower bound for depth 2 threshold circuits with AND gates at the bottom. We will see a degree-discrepency which says that if the sign degree of the base function is large, then the discrepancy of it's lift is small.
In our work, we observed that masking the Universal Threshold function which is a linear threshold function also gives rise to a function which has small discrepancy. Thereby, we show that for a lifted function to be hard, the base function need not have high sign degree.
The communication complexity approach for proving lower bounds is based on the observation that depth 2 circuits with a threshold gate at the top and a small number of low communication gates at the bottom have efficient randomized protocols. So, one approach for proving lower bounds for the above mentioned classes of circuits is to produce a function which has small discrepancy. The lower bound follows from the well known result that functions with small discrepancy have large randomized communication complexity.
The function with small discrepancy is obtained by lifting a base function with large sign degree by a process called masking. This method of lifting to obtain hard functions was used by Krause and Pudlak to obtain functions with large sign monomial complexity from a base function with large sign degree. This shows an exponential lower bound for depth 2 threshold circuits with AND gates at the bottom. We will see a degree-discrepency which says that if the sign degree of the base function is large, then the discrepancy of it's lift is small.
In our work, we observed that masking the Universal Threshold function which is a linear threshold function also gives rise to a function which has small discrepancy. Thereby, we show that for a lifted function to be hard, the base function need not have high sign degree.