Oblivious Classes Revisited: Lower Bounds and Hierarchies

February 07, 2025 • Karthik Gajulapalli

2025   ·   computational   complexity     ·   spring-2025  

Speaker 

Karthik Gajulapalli February 7, 2025. 

Abstract

In this talk we will look at the oblivious counter parts of some popular complexity classes.  We will see the resolution of two very interesting open problems: 1) A fixed polynomial circuit lower bound for a uniform class contained in P/poly 2) A uniform hierarchy theorem of a semantic class that contains BPP.

Our results follow via the powerful range avoidance framework, and the notion of  “uniformly-sparse extensions” , our main technical contribution, that might be of independent interest.



Enjoy Reading This Article?

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

  • Demystifying the border of depth-3 algebraic circuits
  • On Probabilistic Approximations of Boolean Functions via Polynomials, and Polynomial Closure Statements over the Boolean Cube
  • Are quantum speedups for learning expressive classes possible?
  • Borders, Debordering, and Algebraic Complexity
  • Approximating CSPs in the streaming setting