Speaker: |
Tulasi mohan Molli |

Organiser: |
Anamay Tengse |

Date: |
Wednesday, 29 Aug 2018, 17:15 to 18:15 |

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

(Scan to add to calendar)

Classical results show that the probabilistic degree of OR over reals is at most O(log n * log (1/\eps)). We will begin by showing a slight improvement of this upper bound to O( (log n - log log (1/\eps)* log(1/\eps)). It is open if this bound is tight.

In all known upper bounds (including the above improvement), the polynomials have a special structure: they are essentially product of linear forms. We will show for this type of polynomials, the above upper bound is essentially tight.