Speaker: |
Nikhil S Mande |

Organiser: |
Gunjan Kumar |

Date: |
Friday, 21 Oct 2016, 16:00 to 17:30 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

We make progress on the above conjecture by proving strong lower bounds when f is periodic with period n^{1/2 - epsilon} for any constant epsilon > 0. More precisely, we show that every such XOR function has unbounded error complexity n^{Omega(1)}, unless f is a constant or parity or its complement, in which case the complexity is just O(1). As a direct consequence of this, we derive new exponential lower bounds on the size of depth-2 threshold circuits computing such XOR functions (this is based on joint work with Arkadev Chattopadhyay).