research
∙
09/18/2023
A Tight Lower Bound of Ω(log n) for the Estimation of the Number of Defective Items
Let X be a set of items of size n , which may contain some defective ite...
share
research
∙
08/15/2023
Improved Lower Bound for Estimating the Number of Defective Items
Let X be a set of items of size n that contains some defective items, de...
research
∙
06/27/2023
On Detecting Some Defective Items in Group Testing
Group testing is an approach aimed at identifying up to d defective item...
research
∙
01/20/2023
Superpolynomial Lower Bounds for Learning Monotone Classes
Koch, Strassle, and Tan [SODA 2023], show that, under the randomized exp...
research
∙
01/11/2023
A Note on Property Testing of the Binary Rank
Let M be a n× m (0,1)-matrix. We define the s-binary rank, br_s(M), of M...
research
∙
02/07/2022
Almost Optimal Proper Learning and Testing Polynomials
We give the first almost optimal polynomial-time proper learning algorit...
research
∙
08/10/2021
On Learning and Testing Decision Tree
In this paper, we study learning and testing decision tree of size and d...
research
∙
09/05/2020
Optimal Deterministic Group Testing Algorithms to Estimate the Number of Defectives
We study the problem of estimating the number of defective items d withi...
research
∙
06/08/2020
An Optimal Tester for k-Linear
A Boolean function f:{0,1}^n→{0,1} is k-linear if it returns the sum (ov...
research
∙
04/09/2020
Lecture Note on LCSSX's Lower Bounds for Non-Adaptive Distribution-free Property Testing
In this lecture note we give Liu-Chen-Servedio-Sheng-Xie's (LCSSX) lower...
research
∙
01/02/2020
Optimal Randomized Group Testing Algorithm to Determine the Number of Defectives
We study the problem of determining exactly the number of defective item...
research
∙
11/05/2019
Bounds for the Number of Tests in Non-Adaptive Randomized Algorithms for Group Testing
We study the group testing problem with non-adaptive randomized algorith...
research
∙
04/22/2019
Almost Optimal Testers for Concise Representations
We give improved and almost optimal testers for several classes of Boole...
research
∙
01/23/2019
Adaptive Exact Learning of Decision Trees from Membership Queries
In this paper we study the adaptive learnability of decision trees of de...
research
∙
01/01/2019
Almost Optimal Distribution-free Junta Testing
We consider the problem of testing whether an unknown n-variable Boolean...
research
∙
03/28/2018
On Learning Graphs with Edge-Detecting Queries
We consider the problem of learning a general graph G=(V,E) using edge-d...
research
∙
02/01/2018
On Polynomial time Constructions of Minimum Height Decision Tree
In this paper we study a polynomial time algorithms that for an input A⊆...
research
∙
12/02/2017
