4 papers
Faster exact learning of k-term DNFs with membership and equivalence queries
Josh Alman, Shivam Nadimpalli, Shyamal Patel +1
In 1992 Blum and Rudich [BR92] gave an algorithm that uses membership and equivalence queries to learn -term DNF formulas over in time , improv…
DNF Learning via Locally Mixing Random Walks
Josh Alman, Shivam Nadimpalli, Shyamal Patel +1
We give two results on PAC learning DNF formulas using membership queries in the challenging "distribution-free" learning framework, where learning algorithms must succeed for an a…
A Simple Algorithm for Dynamic Carpooling with Recourse
Yuval Efron, Shyamal Patel, Cliff Stein
We give an algorithm for the fully-dynamic carpooling problem with recourse: Edges arrive and depart online from a graph with nodes according to an adaptive adversary. Our…
Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators
Shivam Nadimpalli, Shyamal Patel
We give a non-adaptive algorithm that makes queries to a Boolean function and d…