activity
20152021
most citedLearning and Testing Junta Distributions with Subcube Conditioning

6 citations · 9 across the 4 of their papers we have counts for

collaborators
Showing 2018Show all

2 papers · 1 filter

cs.DS2018

Sublinear-Time Quadratic Minimization via Spectral Decomposition of Matrices

Amit Levi, Yuichi Yoshida

We design a sublinear-time approximation algorithm for quadratic function minimization problems with a better error bound than the previous algorithm by Hayashi and Yoshida (NIPS'1…

cs.CC2018

Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs

Amit Levi, Erik Waingarten

We introduce a new model for testing graph properties which we call the \emph{rejection sampling model}. We show that testing bipartiteness of -nodes graphs using rejection samp…