11 Search Results for "Bshouty, Nader H."


Document
RANDOM
Superpolynomial Lower Bounds for Learning Monotone Classes

Authors: Nader H. Bshouty

Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)


Abstract
Koch, Strassle, and Tan [SODA 2023], show that, under the randomized exponential time hypothesis, there is no distribution-free PAC-learning algorithm that runs in time n^Õ(log log s) for the classes of n-variable size-s DNF, size-s Decision Tree, and log s-Junta by DNF (that returns a DNF hypothesis). Assuming a natural conjecture on the hardness of set cover, they give the lower bound n^Ω(log s). This matches the best known upper bound for n-variable size-s Decision Tree, and log s-Junta. In this paper, we give the same lower bounds for PAC-learning of n-variable size-s Monotone DNF, size-s Monotone Decision Tree, and Monotone log s-Junta by DNF. This solves the open problem proposed by Koch, Strassle, and Tan and subsumes the above results. The lower bound holds, even if the learner knows the distribution, can draw a sample according to the distribution in polynomial time, and can compute the target function on all the points of the support of the distribution in polynomial time.

Cite as

Nader H. Bshouty. Superpolynomial Lower Bounds for Learning Monotone Classes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 34:1-34:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{bshouty:LIPIcs.APPROX/RANDOM.2023.34,
  author =	{Bshouty, Nader H.},
  title =	{{Superpolynomial Lower Bounds for Learning Monotone Classes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{34:1--34:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.34},
  URN =		{urn:nbn:de:0030-drops-188594},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.34},
  annote =	{Keywords: PAC Learning, Monotone DNF, Monotone Decision Tree, Monotone Junta, Lower Bound}
}
Document
On Property Testing of the Binary Rank

Authors: Nader H. Bshouty

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)


Abstract
Let M be an n × m (0,1)-matrix. We define the s-binary rank, denoted as br_s(M), of M as the minimum integer d such that there exist d monochromatic rectangles covering all the 1-entries in the matrix, with each 1-entry being covered by at most s rectangles. When s = 1, this corresponds to the binary rank, denoted as br(M), which is well-known in the literature and has many applications. Let R(M) and C(M) denote the sets of rows and columns of M, respectively. Using the result of Sgall [Jiří Sgall, 1999], we establish that if M has an s-binary rank at most d, then |R(M)| ⋅ |C(M)| ≤ binom(d, ≤ s)2^d, where binom(d, ≤ s) = ∑_{i=0}^s binom(d,i). This bound is tight, meaning that there exists a matrix M' with an s-binary rank of d, for which |R(M')| ⋅ |C(M')| = binom(d, ≤ s)2^d. Using this result, we present novel one-sided adaptive and non-adaptive testers for (0,1)-matrices with an s-binary rank at most d (and exactly d). These testers require Õ(binom(d, ≤ s)2^d/ε) and Õ(binom(d, ≤ s)2^d/ε²) queries, respectively. For a fixed s, this improves upon the query complexity of the tester proposed by Parnas et al. in [Michal Parnas et al., 2021] by a factor of Θ(2^d).

Cite as

Nader H. Bshouty. On Property Testing of the Binary Rank. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{bshouty:LIPIcs.MFCS.2023.27,
  author =	{Bshouty, Nader H.},
  title =	{{On Property Testing of the Binary Rank}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{27:1--27:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.27},
  URN =		{urn:nbn:de:0030-drops-185616},
  doi =		{10.4230/LIPIcs.MFCS.2023.27},
  annote =	{Keywords: Property testing, binary rank, Boolean rank}
}
Document
On the Multilinear Complexity of Associative Algebras

Authors: Markus Bläser, Hendrik Mayer, and Devansh Shringi

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)


Abstract
Christandl and Zuiddam [Matthias Christandl and Jeroen Zuiddam, 2019] study the multilinear complexity of d-fold matrix multiplication in the context of quantum communication complexity. Bshouty [Nader H. Bshouty, 2013] investigates the multilinear complexity of d-fold multiplication in commutative algebras to understand the size of so-called testers. The study of bilinear complexity is a classical topic in algebraic complexity theory, starting with the work by Strassen. However, there has been no systematic study of the multilinear complexity of multilinear maps. In the present work, we systematically investigate the multilinear complexity of d-fold multiplication in arbitrary associative algebras. We prove a multilinear generalization of the famous Alder-Strassen theorem, which is a lower bound for the bilinear complexity of the (2-fold) multiplication in an associative algebra. We show that the multilinear complexity of the d-fold multiplication has a lower bound of d ⋅ dim A - (d-1)t, where t is the number of maximal twosided ideals in A. This is optimal in the sense that there are algebras for which this lower bound is tight. Furthermore, we prove the following dichotomy that the quotient algebra A/rad A determines the complexity of the d-fold multiplication in A: When the semisimple algebra A/rad A is commutative, then the multilinear complexity of the d-fold multiplication in A is polynomial in d. On the other hand, when A/rad A is noncommutative, then the multilinear complexity of the d-fold multiplication in A is exponential in d.

Cite as

Markus Bläser, Hendrik Mayer, and Devansh Shringi. On the Multilinear Complexity of Associative Algebras. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 12:1-12:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{blaser_et_al:LIPIcs.STACS.2023.12,
  author =	{Bl\"{a}ser, Markus and Mayer, Hendrik and Shringi, Devansh},
  title =	{{On the Multilinear Complexity of Associative Algebras}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{12:1--12:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.12},
  URN =		{urn:nbn:de:0030-drops-176645},
  doi =		{10.4230/LIPIcs.STACS.2023.12},
  annote =	{Keywords: Multilinear computations, associative algebras, matrix multiplication, Alder-Strassen theorem}
}
Document
Non-Adaptive Proper Learning Polynomials

Authors: Nader H. Bshouty

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)


Abstract
We give the first polynomial-time non-adaptive proper learning algorithm of Boolean sparse multivariate polynomial under the uniform distribution. Our algorithm, for s-sparse polynomial over n variables, makes q = (s/ε)^{γ(s,ε)}log n queries where 2.66 ≤ γ(s,ε) ≤ 6.922 and runs in Õ(n)⋅ poly(s,1/ε) time. We also show that for any ε = 1/s^{O(1)} any non-adaptive learning algorithm must make at least (s/ε)^{Ω(1)}log n queries. Therefore, the query complexity of our algorithm is also polynomial in the optimal query complexity and optimal in n.

Cite as

Nader H. Bshouty. Non-Adaptive Proper Learning Polynomials. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 16:1-16:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{bshouty:LIPIcs.STACS.2023.16,
  author =	{Bshouty, Nader H.},
  title =	{{Non-Adaptive Proper Learning Polynomials}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{16:1--16:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.16},
  URN =		{urn:nbn:de:0030-drops-176689},
  doi =		{10.4230/LIPIcs.STACS.2023.16},
  annote =	{Keywords: Polynomial, Learning, Testing}
}
Document
On Testing Decision Tree

Authors: Nader H. Bshouty and Catherine A. Haddad-Zaknoon

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)


Abstract
In this paper, we study testing decision tree of size and depth that are significantly smaller than the number of attributes n. Our main result addresses the problem of poly(n,1/ε) time algorithms with poly(s,1/ε) query complexity (independent of n) that distinguish between functions that are decision trees of size s from functions that are ε-far from any decision tree of size ϕ(s,1/ε), for some function ϕ > s. The best known result is the recent one that follows from Blanc, Lange and Tan, [Guy Blanc et al., 2020], that gives ϕ(s,1/ε) = 2^{O((log³s)/ε³)}. In this paper, we give a new algorithm that achieves ϕ(s,1/ε) = 2^{O(log² (s/ε))}. Moreover, we study the testability of depth-d decision tree and give a distribution free tester that distinguishes between depth-d decision tree and functions that are ε-far from depth-d² decision tree.

Cite as

Nader H. Bshouty and Catherine A. Haddad-Zaknoon. On Testing Decision Tree. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{bshouty_et_al:LIPIcs.STACS.2022.17,
  author =	{Bshouty, Nader H. and Haddad-Zaknoon, Catherine A.},
  title =	{{On Testing Decision Tree}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{17:1--17:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.17},
  URN =		{urn:nbn:de:0030-drops-158273},
  doi =		{10.4230/LIPIcs.STACS.2022.17},
  annote =	{Keywords: Testing decision trees}
}
Document
RANDOM
Almost Optimal Testers for Concise Representations

Authors: Nader H. Bshouty

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)


Abstract
We give improved and almost optimal testers for several classes of Boolean functions on n variables that have concise representation in the uniform and distribution-free model. Classes, such as k-Junta, k-Linear, s-Term DNF, s-Term Monotone DNF, r-DNF, Decision List, r-Decision List, size-s Decision Tree, size-s Boolean Formula, size-s Branching Program, s-Sparse Polynomial over the binary field and functions with Fourier Degree at most d. The approach is new and combines ideas from Diakonikolas et al. [Ilias Diakonikolas et al., 2007], Bshouty [Nader H. Bshouty, 2018], Goldreich et al. [Oded Goldreich et al., 1998], and learning theory. The method can be extended to several other classes of functions over any domain that can be approximated by functions with a small number of relevant variables.

Cite as

Nader H. Bshouty. Almost Optimal Testers for Concise Representations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{bshouty:LIPIcs.APPROX/RANDOM.2020.5,
  author =	{Bshouty, Nader H.},
  title =	{{Almost Optimal Testers for Concise Representations}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{5:1--5:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.5},
  URN =		{urn:nbn:de:0030-drops-126087},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.5},
  annote =	{Keywords: Property Testing, Boolean function, Junta}
}
Document
Optimal Randomized Group Testing Algorithm to Determine the Number of Defectives

Authors: Nader H. Bshouty, Catherine A. Haddad-Zaknoon, Raghd Boulos, Foad Moalem, Jalal Nada, Elias Noufi, and Yara Zaknoon

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)


Abstract
We study the problem of determining the exact number of defective items in an adaptive group testing by using a minimum number of tests. We improve the existing algorithm and prove a lower bound that shows that the number of tests in our algorithm is optimal up to small additive terms.

Cite as

Nader H. Bshouty, Catherine A. Haddad-Zaknoon, Raghd Boulos, Foad Moalem, Jalal Nada, Elias Noufi, and Yara Zaknoon. Optimal Randomized Group Testing Algorithm to Determine the Number of Defectives. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 18:1-18:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{bshouty_et_al:LIPIcs.SWAT.2020.18,
  author =	{Bshouty, Nader H. and Haddad-Zaknoon, Catherine A. and Boulos, Raghd and Moalem, Foad and Nada, Jalal and Noufi, Elias and Zaknoon, Yara},
  title =	{{Optimal Randomized Group Testing Algorithm to Determine the Number of Defectives}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{18:1--18:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.18},
  URN =		{urn:nbn:de:0030-drops-122658},
  doi =		{10.4230/LIPIcs.SWAT.2020.18},
  annote =	{Keywords: Group Testing, Randomized Algorithm}
}
Document
Lower Bound for Non-Adaptive Estimation of the Number of Defective Items

Authors: Nader H. Bshouty

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)


Abstract
We prove that to estimate within a constant factor the number of defective items in a non-adaptive randomized group testing algorithm we need at least Omega~(log n) tests. This solves the open problem posed by Damaschke and Sheikh Muhammad in [Peter Damaschke and Azam Sheikh Muhammad, 2010; Peter Damaschke and Azam Sheikh Muhammad, 2010].

Cite as

Nader H. Bshouty. Lower Bound for Non-Adaptive Estimation of the Number of Defective Items. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 2:1-2:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{bshouty:LIPIcs.ISAAC.2019.2,
  author =	{Bshouty, Nader H.},
  title =	{{Lower Bound for Non-Adaptive Estimation of the Number of Defective Items}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{2:1--2:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.2},
  URN =		{urn:nbn:de:0030-drops-114983},
  doi =		{10.4230/LIPIcs.ISAAC.2019.2},
  annote =	{Keywords: Group Testing, Estimation, Defective Items}
}
Document
Almost Optimal Distribution-Free Junta Testing

Authors: Nader H. Bshouty

Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)


Abstract
We consider the problem of testing whether an unknown n-variable Boolean function is a k-junta in the distribution-free property testing model, where the distance between functions is measured with respect to an arbitrary and unknown probability distribution over {0,1}^n. Chen, Liu, Servedio, Sheng and Xie [Zhengyang Liu et al., 2018] showed that the distribution-free k-junta testing can be performed, with one-sided error, by an adaptive algorithm that makes O~(k^2)/epsilon queries. In this paper, we give a simple two-sided error adaptive algorithm that makes O~(k/epsilon) queries.

Cite as

Nader H. Bshouty. Almost Optimal Distribution-Free Junta Testing. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 2:1-2:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{bshouty:LIPIcs.CCC.2019.2,
  author =	{Bshouty, Nader H.},
  title =	{{Almost Optimal Distribution-Free Junta Testing}},
  booktitle =	{34th Computational Complexity Conference (CCC 2019)},
  pages =	{2:1--2:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-116-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{137},
  editor =	{Shpilka, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.2},
  URN =		{urn:nbn:de:0030-drops-108249},
  doi =		{10.4230/LIPIcs.CCC.2019.2},
  annote =	{Keywords: Distribution-free property testing, k-Junta}
}
Document
On Polynomial Time Constructions of Minimum Height Decision Tree

Authors: Nader H. Bshouty and Waseem Makhoul

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)


Abstract
A decision tree T in B_m:={0,1}^m is a binary tree where each of its internal nodes is labeled with an integer in [m]={1,2,...,m}, each leaf is labeled with an assignment a in B_m and each internal node has two outgoing edges that are labeled with 0 and 1, respectively. Let A subset {0,1}^m. We say that T is a decision tree for A if (1) For every a in A there is one leaf of T that is labeled with a. (2) For every path from the root to a leaf with internal nodes labeled with i_1,i_2,...,i_k in[m], a leaf labeled with a in A and edges labeled with xi_{i_1},...,xi_{i_k}in {0,1}, a is the only element in A that satisfies a_{i_j}=xi_{i_j} for all j=1,...,k. Our goal is to write a polynomial time (in n:=|A| and m) algorithm that for an input A subseteq B_m outputs a decision tree for A of minimum depth. This problem has many applications that include, to name a few, computer vision, group testing, exact learning from membership queries and game theory. Arkin et al. and Moshkov [Esther M. Arkin et al., 1998; Mikhail Ju. Moshkov, 2004] gave a polynomial time (ln |A|)- approximation algorithm (for the depth). The result of Dinur and Steurer [Irit Dinur and David Steurer, 2014] for set cover implies that this problem cannot be approximated with ratio (1-o(1))* ln |A|, unless P=NP. Moshkov studied in [Mikhail Ju. Moshkov, 2004; Mikhail Ju. Moshkov, 1982; Mikhail Ju. Moshkov, 1982] the combinatorial measure of extended teaching dimension of A, ETD(A). He showed that ETD(A) is a lower bound for the depth of the decision tree for A and then gave an exponential time ETD(A)/log(ETD(A))-approximation algorithm and a polynomial time 2(ln 2)ETD(A)-approximation algorithm. In this paper we further study the ETD(A) measure and a new combinatorial measure, DEN(A), that we call the density of the set A. We show that DEN(A) <=ETD(A)+1. We then give two results. The first result is that the lower bound ETD(A) of Moshkov for the depth of the decision tree for A is greater than the bounds that are obtained by the classical technique used in the literature. The second result is a polynomial time (ln 2)DEN(A)-approximation (and therefore (ln 2)ETD(A)-approximation) algorithm for the depth of the decision tree of A. We then apply the above results to learning the class of disjunctions of predicates from membership queries [Nader H. Bshouty et al., 2017]. We show that the ETD of this class is bounded from above by the degree d of its Hasse diagram. We then show that Moshkov algorithm can be run in polynomial time and is (d/log d)-approximation algorithm. This gives optimal algorithms when the degree is constant. For example, learning axis parallel rays over constant dimension space.

Cite as

Nader H. Bshouty and Waseem Makhoul. On Polynomial Time Constructions of Minimum Height Decision Tree. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 34:1-34:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{h.bshouty_et_al:LIPIcs.ISAAC.2018.34,
  author =	{H. Bshouty, Nader and Makhoul, Waseem},
  title =	{{On Polynomial Time Constructions of Minimum Height Decision Tree}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{34:1--34:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.34},
  URN =		{urn:nbn:de:0030-drops-99824},
  doi =		{10.4230/LIPIcs.ISAAC.2018.34},
  annote =	{Keywords: Decision Tree, Minimal Depth, Approximation algorithms}
}
Document
Optimal Query Complexity for Reconstructing Hypergraphs

Authors: Nader H. Bshouty and Hanna Mazzawi

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)


Abstract
In this paper we consider the problem of reconstructing a hidden weighted hypergraph of constant rank using additive queries. We prove the following: Let $G$ be a weighted hidden hypergraph of constant rank with~$n$ vertices and $m$ hyperedges. For any $m$ there exists a non-adaptive algorithm that finds the edges of the graph and their weights using $$ O\left(\frac{m\log n}{\log m}\right) $$ additive queries. This solves the open problem in [S. Choi, J. H. Kim. Optimal Query Complexity Bounds for Finding Graphs. {\em STOC}, 749--758, 2008]. When the weights of the hypergraph are integers that are less than $O(poly(n^d/m))$ where $d$ is the rank of the hypergraph (and therefore for unweighted hypergraphs) there exists a non-adaptive algorithm that finds the edges of the graph and their weights using $$ O\left(\frac{m\log \frac{n^d}{m}}{\log m}\right). $$ additive queries. Using the information theoretic bound the above query complexities are tight.

Cite as

Nader H. Bshouty and Hanna Mazzawi. Optimal Query Complexity for Reconstructing Hypergraphs. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 143-154, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{bshouty_et_al:LIPIcs.STACS.2010.2496,
  author =	{Bshouty, Nader H. and Mazzawi, Hanna},
  title =	{{Optimal Query Complexity for Reconstructing Hypergraphs}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{143--154},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2496},
  URN =		{urn:nbn:de:0030-drops-24968},
  doi =		{10.4230/LIPIcs.STACS.2010.2496},
  annote =	{Keywords: Query complexity, hypergraphs}
}
  • Refine by Author
  • 9 Bshouty, Nader H.
  • 2 Haddad-Zaknoon, Catherine A.
  • 1 Bläser, Markus
  • 1 Boulos, Raghd
  • 1 H. Bshouty, Nader
  • Show More...

  • Refine by Classification
  • 5 Mathematics of computing
  • 4 Mathematics of computing → Discrete mathematics
  • 4 Mathematics of computing → Probabilistic algorithms
  • 4 Theory of computation → Probabilistic computation
  • 3 Theory of computation
  • Show More...

  • Refine by Keyword
  • 2 Group Testing
  • 1 Alder-Strassen theorem
  • 1 Approximation algorithms
  • 1 Boolean function
  • 1 Boolean rank
  • Show More...

  • Refine by Type
  • 11 document

  • Refine by Publication Year
  • 4 2023
  • 2 2019
  • 2 2020
  • 1 2010
  • 1 2018
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail