Tata Institute of Fundamental Research
On the Probabilistic Degrees of Symmetric Boolean Functions
STCS Student Seminar
Speaker:
S. Venkitesh ((Math, IITB))
Organiser:
Vidya Sagar Sharma
Date:
Friday, 6 Dec 2019, 14:30 to 15:30
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: The probabilistic degree of a Boolean function f is defined to be the smallest d such that there is a random polynomial P of degree at most d that agrees with f at each point with high probability. Introduced by Razborov (1987), upper and lower bounds on probabilistic degrees of Boolean functions --- specifically symmetric Boolean functions --- have been used to prove explicit lower bounds, design pseudorandom generators, and devise algorithms for combinatorial problems.
We will characterize the probabilistic degrees of all symmetric Boolean functions up to polylogarithmic factors over all fields of fixed characteristic (positive or zero).
This is joint work with Srikanth Srinivasan and Utkarsh Tripathi.
| Speaker: | S. Venkitesh ((Math, IITB)) |
| Organiser: | Vidya Sagar Sharma |
| Date: | Friday, 6 Dec 2019, 14:30 to 15:30 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: The probabilistic degree of a Boolean function f is defined to be the smallest d such that there is a random polynomial P of degree at most d that agrees with f at each point with high probability. Introduced by Razborov (1987), upper and lower bounds on probabilistic degrees of Boolean functions --- specifically symmetric Boolean functions --- have been used to prove explicit lower bounds, design pseudorandom generators, and devise algorithms for combinatorial problems.
We will characterize the probabilistic degrees of all symmetric Boolean functions up to polylogarithmic factors over all fields of fixed characteristic (positive or zero).
This is joint work with Srikanth Srinivasan and Utkarsh Tripathi.
We will characterize the probabilistic degrees of all symmetric Boolean functions up to polylogarithmic factors over all fields of fixed characteristic (positive or zero).
This is joint work with Srikanth Srinivasan and Utkarsh Tripathi.