On learning thresholds of parities and unions of rectangles in random walk models

DOI10.1002/rsa.20162zbMath1147.68035arXivcs/0605048OpenAlexW2952733307MaRDI QIDQ5433270

Sebastien Roch

Publication date: 8 January 2008

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0605048

zbMATH Keywords

PAC learningrandom walk modelstatistical queriesthresholds of parities

Mathematics Subject Classification ID

Computational learning theory (68Q32) Sums of independent random variables; random walks (60G50)

Cites Work

• Weakly learning DNF and characterizing statistical query learning using Fourier analysis
• Gaussian Hilbert Spaces
• Efficient learning of typical finite automata from random walks
• Unnamed Item

This page was built for publication: On learning thresholds of parities and unions of rectangles in random walk models