Events

IFML Seminar

IFML Seminar: 10/16/26 - Faster Algorithms for Learning k-Term DNFs with Queries

Shyamal Patel, IFML Postdoctoral Fellow

-

The University of Texas at Austin
Gates Dell Complex (GDC 6.302)
2317 Speedway
Austin, TX 78712
United States

ifml_seminar_101626

Abstract: A fundamental task in learning theory is to understand the computational complexity of learning k-term DNFs in the distribution-free PAC learning model. Unfortunately, given only random examples, a variety of lower bounds suggest that learning DNFs with a superconstant number of terms requires superpolynomial time. That said, work by Blum and Rudich showed that such a bound can be circumvented if we have query access to the function, proving k-term DNFs can be learned in time n*2^k in this setting.

In this talk, we’ll describe an algorithm to learn k-term DNFs in time n*2^{sqrt{k}}. To do so, we construct an adaptive set of features that allow us to represent the function as the sign of a low-degree polynomial over these features. We then use tools from junta testing and attribute-efficient learning to effectively reduce the number of variables and achieve our result.

Based on joint work with Josh Alman, Shivam Nadimpalli, and Rocco Servedio.


Bio: Dr. Shyamal Patel is an IFML Postdoctoral Fellow at UT Austin interested in computational learning theory and property testing. He received his PhD in computer science from Columbia University, where he was advised by Clifford Stein and Xi Chen.

Zoom link: https://utexas.zoom.us/j/89110047398