# Nader H. Bshouty

According to our database

Collaborative distances:

^{1}, Nader H. Bshouty authored at least 144 papers between 1987 and 2020.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepages:

#### On csauthors.net:

## Bibliography

2020

Optimal Randomized Group Testing Algorithm to Determine the Number of Defectives.

CoRR, 2020

Bounds for the Number of Tests in Non-adaptive Randomized Algorithms for Group Testing.

Proceedings of the SOFSEM 2020: Theory and Practice of Computer Science, 2020

2019

Almost Optimal Testers for Concise Representations.

Electronic Colloquium on Computational Complexity (ECCC), 2019

Lower Bound for Non-Adaptive Estimation of the Number of Defective Items.

Proceedings of the 30th International Symposium on Algorithms and Computation, 2019

Almost Optimal Distribution-Free Junta Testing.

Proceedings of the 34th Computational Complexity Conference, 2019

Adaptive Exact Learning of Decision Trees from Membership Queries.

Proceedings of the Algorithmic Learning Theory, 2019

On Learning Graphs with Edge-Detecting Queries.

Proceedings of the Algorithmic Learning Theory, 2019

2018

Exact learning of juntas from membership queries.

Theor. Comput. Sci., 2018

Exact learning from an honest teacher that answers membership queries.

Theor. Comput. Sci., 2018

Non-adaptive learning of a hidden hypergraph.

Theor. Comput. Sci., 2018

Lower Bound for Non-Adaptive Estimate the Number of Defective Items.

Electronic Colloquium on Computational Complexity (ECCC), 2018

Elementary Proofs of Some Stirling Bounds.

CoRR, 2018

On Polynomial Time Constructions of Minimum Height Decision Tree.

Proceedings of the 29th International Symposium on Algorithms and Computation, 2018

Adaptive Group Testing Algorithms to Estimate the Number of Defectives.

Proceedings of the Algorithmic Learning Theory, 2018

2017

Learning Disjunctions of Predicates.

Proceedings of the 30th Conference on Learning Theory, 2017

Almost Optimal Cover-Free Families.

Proceedings of the Algorithms and Complexity - 10th International Conference, 2017

Non-Adaptive Randomized Algorithm for Group Testing.

Proceedings of the International Conference on Algorithmic Learning Theory, 2017

2016

Learning boolean halfspaces with small weights from membership queries.

Theor. Comput. Sci., 2016

Derandomizing Chernoff Bound with Union Bound with an Application to

*k*-wise Independent Sets.
Electronic Colloquium on Computational Complexity (ECCC), 2016

Enumerating all the Irreducible Polynomials over Finite Field.

CoRR, 2016

Derandomizing Chernoff Bound with Union Bound with an Application to $k$-wise Independent Sets.

CoRR, 2016

Lower Bounds for Cover-Free Families.

Electr. J. Comb., 2016

The Maximum Cosine Framework for Deriving Perceptron Based Linear Classifiers.

Proceedings of the Algorithmic Learning Theory - 27th International Conference, 2016

2015

On Parity Check (0, 1)-Matrix over ℤ

_{p}.
SIAM J. Discrete Math., 2015

Dense Testers: Almost Linear Time and Locally Explicit Constructions.

Electronic Colloquium on Computational Complexity (ECCC), 2015

Non-Adaptive Learning a Hidden Hipergraph.

CoRR, 2015

Linear Time Constructions of Some d -Restriction Problems.

Proceedings of the Algorithms and Complexity - 9th International Conference, 2015

2014

Guest Editors' foreword.

Theor. Comput. Sci., 2014

Electronic Colloquium on Computational Complexity (ECCC), 2014

A Simple Algorithm for Hamiltonicity.

CoRR, 2014

On r-Simple k-Path.

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

On Exact Learning Monotone DNF from Membership Queries.

Proceedings of the Algorithmic Learning Theory - 25th International Conference, 2014

2013

Multilinear Complexity is Equivalent to Optimal Tester Size.

Electronic Colloquium on Computational Complexity (ECCC), 2013

A Simple Algorithm for Undirected Hamiltonicity.

Electronic Colloquium on Computational Complexity (ECCC), 2013

Exact Learning from Membership Queries: Some Techniques, Results and New Directions.

Proceedings of the Algorithmic Learning Theory - 24th International Conference, 2013

2012

Toward a deterministic polynomial time algorithm with optimal additive query complexity.

Theor. Comput. Sci., 2012

Linear classifiers are nearly optimal when hidden variables have diverse effects.

Machine Learning, 2012

Testers and their Applications.

Electronic Colloquium on Computational Complexity (ECCC), 2012

Testers.

ACM Comm. Computer Algebra, 2012

On the Coin Weighing Problem with the Presence of Noise.

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

Editors' Introduction.

Proceedings of the Algorithmic Learning Theory - 23rd International Conference, 2012

2011

Reconstructing weighted graphs with minimal query complexity.

Theor. Comput. Sci., 2011

Algorithms for the Coin Weighing Problems with the Presence of Noise.

Electronic Colloquium on Computational Complexity (ECCC), 2011

On Parity Check (0, 1)-Matrix over Z

^{p}.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

2010

Optimal Query Complexity for Reconstructing Hypergraphs.

Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

Finding Planted Partitions in Nearly Linear Time using Arrested Spectral Clustering.

Proceedings of the 27th International Conference on Machine Learning (ICML-10), 2010

2009

Using the doubling dimension to analyze the generalization of learning algorithms.

J. Comput. Syst. Sci., 2009

Linear Classifiers are Nearly Optimal When Hidden Variables Have Diverse Effect.

Proceedings of the COLT 2009, 2009

Optimal Algorithms for the Coin Weighing Problem with a Spring Scale.

Proceedings of the COLT 2009, 2009

2008

Learning Automata.

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Guest Editors' Introduction: Special issue on Learning Theory (COLT-2007).

Machine Learning, 2008

Learning with errors in answers to membership queries.

J. Comput. Syst. Sci., 2008

2007

Learning attribute-efficiently with corrupt oracles.

Theor. Comput. Sci., 2007

2006

Maximizing agreements and coagnostic learning.

Theor. Comput. Sci., 2006

Polynomial multiplication over finite fields: from quadratic to straight-line complexity.

Computational Complexity, 2006

Exact Learning Composed Classes with a Small Number of Mistakes.

Proceedings of the Learning Theory, 19th Annual Conference on Learning Theory, 2006

On Optimal Learning Algorithms for Multiplicity Automata.

Proceedings of the Learning Theory, 19th Annual Conference on Learning Theory, 2006

On Exact Learning Halfspaces with Random Consistent Hypothesis Oracle.

Proceedings of the Algorithmic Learning Theory, 17th International Conference, 2006

On Exact Learning from Random Walk.

Proceedings of the Algorithmic Learning Theory, 17th International Conference, 2006

2005

Maximizing Agreements with One-Sided Error with Applications to Heuristic Learning.

Machine Learning, 2005

Learning DNF from random walks.

J. Comput. Syst. Sci., 2005

Exploring learnability between exact and PAC.

J. Comput. Syst. Sci., 2005

2004

More efficient PAC-learning of DNF with membership queries under the uniform distribution.

J. Comput. Syst. Sci., 2004

Polynomial Time Prediction Strategy with Almost Optimal Mistake Probability.

Proceedings of the Learning Theory, 17th Annual Conference on Learning Theory, 2004

2003

On the Proper Learning of Axis-Parallel Concepts.

J. Mach. Learn. Res., 2003

Uniform-distribution attribute noise learnability.

Inf. Comput., 2003

2002

PAC learning with nasty noise.

Theor. Comput. Sci., 2002

Simple Learning Algorithms for Decision Trees and Multivariate Polynomials.

SIAM J. Comput., 2002

On Boosting with Polynomially Bounded Distributions.

J. Mach. Learn. Res., 2002

On Using Extended Statistical Queries to Avoid Membership Queries.

J. Mach. Learn. Res., 2002

Learning Monotone DNF from a Teacher that Almost Does Not Answer Membership Queries.

J. Mach. Learn. Res., 2002

PAC = PAExact and Other Equivalent Models in Learning.

Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Bounds for the Minimum Disagreement Problem with Applications to Learning Theory.

Proceedings of the Computational Learning Theory, 2002

2001

Learning Regular Sets with an Incomplete Membership Oracle.

Proceedings of the Computational Learning Theory, 2001

On Boosting with Optimal Poly-Bounded Distributions.

Proceedings of the Computational Learning Theory, 2001

2000

Learning functions represented as multiplicity automata.

J. ACM, 2000

1999

Learning DNF over the Uniform Distribution Using a Quantum Example Oracle.

SIAM J. Comput., 1999

Lower Bounds for the Complexity of Functions in a Realistic RAM Model.

J. Algorithms, 1999

Meeting Times of Random Walks on Graphs.

Inf. Process. Lett., 1999

On Learning in the Presence of Unspecified Attribute Values.

Proceedings of the Twelfth Annual Conference on Computational Learning Theory, 1999

Learning Threshold Functions with Small Weights Using Membership Queries.

Proceedings of the Twelfth Annual Conference on Computational Learning Theory, 1999

1998

Exact Learning of Discretized Geometric Concepts.

SIAM J. Comput., 1998

Interpolating Arithmetic Read-Once Formulas in Parallel.

SIAM J. Comput., 1998

Attribute-Efficient Learning in Query and Mistake-Bound Models.

J. Comput. Syst. Sci., 1998

On Interpolating Arithmetic Read-Once Formulas with Exponentiation.

J. Comput. Syst. Sci., 1998

On the Direct Sum Conjecture in the Straight Line Model.

J. Complexity, 1998

Noise-Tolerant Distribution-Free Learning of General Geometric Concepts.

J. ACM, 1998

On Learning width Two Branching Programs.

Inf. Process. Lett., 1998

Noise-Tolerant Parallel Learning of Geometric Concepts.

Inf. Comput., 1998

Attribute Efficient PAC Learning of DNF with Membership Queries under the Uniform Distribution

Electronic Colloquium on Computational Complexity (ECCC), 1998

A New Composition Theorem for Learning Algorithms

Electronic Colloquium on Computational Complexity (ECCC), 1998

Learning Matrix Functions over Rings.

Algorithmica, 1998

On Learning Decision Trees with Large Output Domains.

Algorithmica, 1998

Massaging a Linear Programming Solution to Give a 2-Approximation for a Generalization of the Vertex Cover Problem.

Proceedings of the STACS 98, 1998

1997

Exact Learning of Formulas in Parallel.

Machine Learning, 1997

A Tight Bound for Approximating the Square Root.

Inf. Process. Lett., 1997

On Learning Multivariate Polynomials Under the Uniform Distribution.

Inf. Process. Lett., 1997

Simple Learning Algorithms Using Divide and Conquer.

Computational Complexity, 1997

On Learning Programs and Small Depth Circuits.

Proceedings of the Computational Learning Theory, Third European Conference, 1997

1996

Asking Questions to Minimize Errors.

J. Comput. Syst. Sci., 1996

Oracles and Queries That Are Sufficient for Exact Learning.

J. Comput. Syst. Sci., 1996

On the Fourier Spectrum of Monotone Functions.

J. ACM, 1996

A Subexponential Exact Learning Algorithm for DNF Using Equivalence Queries.

Inf. Process. Lett., 1996

A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes

Electronic Colloquium on Computational Complexity (ECCC), 1996

On Learning Branching Programs and Small Depth Circuits

Electronic Colloquium on Computational Complexity (ECCC), 1996

Learning Multivariate Polynomials from Substitution and Equivalence Queries

Electronic Colloquium on Computational Complexity (ECCC), 1996

Towards the Learnability of DNF Formulae.

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

On the Applications of Multiplicity Automata in Learning.

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

On Learning width Two Branching Programs (Extended Abstract).

Proceedings of the Ninth Annual Conference on Computational Learning Theory, 1996

1995

Learning Arithmetic Read-Once Formulas.

SIAM J. Comput., 1995

Size-Depth Tradeoffs for Algebraic Formulas.

SIAM J. Comput., 1995

Learning Boolean Read-Once Formulas over Generalized Bases.

J. Comput. Syst. Sci., 1995

On the Additive Complexity of 2 x 2 Matrix Multiplication.

Inf. Process. Lett., 1995

Exact Learning Boolean Function via the Monotone Theory.

Inf. Comput., 1995

The Monotone Theory for the PAC-Model

Electronic Colloquium on Computational Complexity (ECCC), 1995

Exact Learning Boolean Functions via the Monotone Theory

Electronic Colloquium on Computational Complexity (ECCC), 1995

On the Fourier spectrum of monotone functions (Extended Abstract).

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

On Learning Decision Trees with Large Output Domains (Extended Abstract).

Proceedings of the Eigth Annual Conference on Computational Learning Theory, 1995

Proceedings of the Eigth Annual Conference on Computational Learning Theory, 1995

A Note on Learning Multivariate Polynomials Under the Uniform Distribution (Extended Abstract).

Proceedings of the Eigth Annual Conference on Computational Learning Theory, 1995

1994

On the Complexity of Bilinear Forms over Associative Algebras.

SIAM J. Comput., 1994

An Algorithm to Learn Read-Once Threshold Formulas, and Transformations Between Learning Models.

Computational Complexity, 1994

On Learning Discretized Geometric Concepts (Extended Abstract)

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

Oracles and Queries that are Sufficient for Exact Learning (Extended Abstract).

Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994

On Learning Arithmetic Read-Once Formulas with Exponentiation (Extended Abstract).

Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994

1993

On the Complexity of Functions for Random Access Machines.

J. ACM, 1993

Exact Learning via the Monotone Theory (Extended Abstract)

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992

A Classification of Algorithms for Multiplying Polynomials of Small Degree over Finite Fields.

J. Algorithms, 1992

A Lower Bound for the Multiplication of Polynomials Modulo a Polynomial.

Inf. Process. Lett., 1992

Fast Exponentiation Using the Truncation Operation.

Computational Complexity, 1992

Compression of Dictionaries via Extensions to Front Coding.

Proceedings of the Computing and Information, 1992

On the Exact Learning of Formulas in Parallel (Extended Abstract)

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

Learning Boolean Read-Once Formulas with Arbitrary Symmetric and Constant Fan-in Gates.

Proceedings of the Fifth Annual ACM Conference on Computational Learning Theory, 1992

1991

Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains.

Proceedings of the Advances in Computing and Information, 1991

Size-Depth Tradeoffs for Algebraic Formulae

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1990

Generalizations of the Normal Basis Theorem of Finite Fields.

SIAM J. Discrete Math., 1990

Multiplication of Polynomials over Finite Fields.

SIAM J. Comput., 1990

Maximal Rank of m x n x (mn - k) Tensors.

SIAM J. Comput., 1990

1989

A Lower Bound for Matrix Multiplication.

SIAM J. Comput., 1989

Multiplicative complexity of polynomial multiplication over finite fields.

J. ACM, 1989

On the Extended Direct Sum Conjecture

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

1988

Vector sets for exhaustive testing of logic circuits.

IEEE Trans. Information Theory, 1988

Addition Requirements for Matrix and Transposed Matrix Products.

J. Algorithms, 1988

1987

Multiplicative complexity of polynomial multiplication over finite fields (Extended abstract)

Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987