1 citations · 3 across the 8 of their papers we have counts for
3 papers · 1 filter
Intractability of Learning the Discrete Logarithm with Gradient-Based Methods
Rustem Takhanov, Maxat Tezekbayev, Artur Pak +3
The discrete logarithm problem is a fundamental challenge in number theory with significant implications for cryptographic protocols. In this paper, we investigate the limitations…
Gradient Descent Fails to Learn High-frequency Functions and Modular Arithmetic
Rustem Takhanov, Maxat Tezekbayev, Artur Pak +2
Classes of target functions containing a large number of approximately orthogonal elements are known to be hard to learn by the Statistical Query algorithms. Recently this classica…
Long-Tail Theory under Gaussian Mixtures
Arman Bolatov, Maxat Tezekbayev, Igor Melnykov +3
We suggest a simple Gaussian mixture model for data generation that complies with Feldman's long tail theory (2020). We demonstrate that a linear classifier cannot decrease the gen…