11 citations · 20 across the 7 of their papers we have counts for
8 papers
Frontier Space-Time Algorithms Using Only Full Memory
Petr Chmel, Aditi Dudeja, Michal Koucký +2
We develop catalytic algorithms for fundamental problems in algorithm design that run in polynomial time, use only workspace, and use sublinear catalytic spa…
On the Power of Interactive Proofs for Learning
Tom Gur, Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh +3
We continue the study of doubly-efficient proof systems for verifying agnostic PAC learning, for which we obtain the following results. - We construct an interactive protocol for l…
Distribution-Free Proofs of Proximity
Hugo Aaronson, Tom Gur, Ninad Rajgopal +1
Motivated by the fact that input distributions are often unknown in advance, distribution-free property testing considers a setting where the algorithmic task is to accept function…
Optimal Testing and Containment Strategies for Universities in Mexico amid COVID-19
Luis Benavides-Vázquez, Héctor Alonso Guzmán-Gutiérrez, Jakob Jonnerby +5
This work sets out a testing and containment framework developed for reopening universities in Mexico following the lockdown due to COVID-19. We treat diagnostic testing as a resou…
Optimally Deceiving a Learning Leader in Stackelberg Games
Georgios Birmpas, Jiarui Gan, Alexandros Hollender +3
Recent results in the ML community have revealed that learning algorithms used to compute the optimal strategy for the leader to commit to in a Stackelberg game, are susceptible to…
Beyond Natural Proofs: Hardness Magnification and Locality
Lijie Chen, Shuichi Hirahara, Igor C. Oliveira +3
Hardness magnification reduces major complexity separations (such as ) to proving lower bounds for some natural problem against…
On learning k-parities with and without noise
Arnab Bhattacharyya, Ameet Gadekar, Ninad Rajgopal
We first consider the problem of learning -parities in the on-line mistake-bound model: given a hidden vector with and a sequence of "questions" $a_1,…
Selection Lemmas for various geometric objects
Pradeesha Ashok, Ninad Rajgopal, Sathish Govindarajan
Selection lemmas are classical results in discrete geometry that have been well studied and have applications in many geometric problems like weak epsilon nets and slimming Delauna…