Lower Bounds on Learning Random Structures with Statistical Queries
From MaRDI portal
Publication:4930699
DOI10.1007/978-3-642-16108-7_18zbMath1306.68047OpenAlexW2106435631MaRDI QIDQ4930699
Lev Reyzin, David Eisenstat, Dana Angluin, Leonid (Aryeh) Kontorovich
Publication date: 1 October 2010
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-16108-7_18
Computational learning theory (68Q32) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items (5)
The state complexity of random DFAs ⋮ VC bounds on the cardinality of nearly orthogonal function classes ⋮ Learning a Random DFA from Uniform Strings and State Information ⋮ Diameter and stationary distribution of random \(r\)-out digraphs ⋮ AN INEQUALITY INVOLVING THE ℓ1, ℓ2, AND ℓ∞ NORMS
This page was built for publication: Lower Bounds on Learning Random Structures with Statistical Queries
