On Probabilistic Approximations of Boolean Functions via Polynomials, and Polynomial Closure Statements over the Boolean Cube

Speaker

S Venkitesh February 02, 2022.

Abstract

Representing Boolean functions by polynomials is a tried-and-tested technique that has found uses in many areas of theoretical computer science, for instance, complexity theory, learning theory, and algorithm design. There are many different kinds of polynomial representations that are useful in various applications, and more often than not, the degree of the polynomial turns out to be an important notion of complexity, with connections to other Boolean function complexity measures.

In this talk, I shall attempt to circle around some of the important relevant literature in complexity theory, as well as talk a bit about my contribution to it (via joint works with my graduate advisor, Srikanth Srinivasan, and others). We will restrict our attention specifically to two notions: (i) probabilistic polynomial – a random polynomial that agrees with a given function with high probability at every input, and (ii) the finite-degree Zariski closure – a classical algebraic object that records the common vanishing set of a collection of polynomials, specified via vanishing conditions and degree constraints on an input set of points. I will try to cover some history, some recent results, as well as mention some open questions.




Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • On the Probabilistic Degree of an n-variate Boolean Function
  • Communication Complexity of Partial XOR Functions
  • Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits
  • A better-than-3 log n depth lower bound for De Morgan formulas with restrictions on top gates
  • Are quantum speedups for learning expressive classes possible?