Tata Institute of Fundamental Research
Unbounded Error Communication Complexity of XOR Functions
STCS Student Seminar
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)
Abstract:
We consider the unbounded error communication complexity of XOR functions, i.e. those of the form f of XOR, where f is an arbitrary boolean function on n bits. An interesting conjecture of Zhang and Shi [ZS'09] asserts that for symmetric f, the unbounded error complexity is essentially characterized by the number of points in {0,..., n-2} for which D(i) doesn't equal D(i + 2), where D is the predicate corresponding to f.
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).
| 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)
Abstract:
We consider the unbounded error communication complexity of XOR functions, i.e. those of the form f of XOR, where f is an arbitrary boolean function on n bits. An interesting conjecture of Zhang and Shi [ZS'09] asserts that for symmetric f, the unbounded error complexity is essentially characterized by the number of points in {0,..., n-2} for which D(i) doesn't equal D(i + 2), where D is the predicate corresponding to f.
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).
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).