Idan Attias
@idanattias.bsky.social
Postdoc researcher at IDEAL Institute in Chicago, hosted by UIC and TTIC.
My research interests are in machine learning theory, data-driven sequential decision-making, and theoretical computer science.
https://www.idanattias.com/
My research interests are in machine learning theory, data-driven sequential decision-making, and theoretical computer science.
https://www.idanattias.com/
A key takeaway is that what truly matters is the complexity measure (or description length, or equivalently ‘prior’) induced by the model, rather than the concept class itself!
October 8, 2025 at 2:37 PM
A key takeaway is that what truly matters is the complexity measure (or description length, or equivalently ‘prior’) induced by the model, rather than the concept class itself!
We prove hardness in the PAC model and in the membership query setting, under distribution-free learning as well as under the uniform distribution.
Note that DFAs are efficiently learnable with membership queries, whereas we prove that REs remain hard in the same model.
Note that DFAs are efficiently learnable with membership queries, whereas we prove that REs remain hard in the same model.
October 8, 2025 at 2:37 PM
We prove hardness in the PAC model and in the membership query setting, under distribution-free learning as well as under the uniform distribution.
Note that DFAs are efficiently learnable with membership queries, whereas we prove that REs remain hard in the same model.
Note that DFAs are efficiently learnable with membership queries, whereas we prove that REs remain hard in the same model.
The important point is that when we say DFAs or REs are easy or hard to learn, we mean that it is easy or hard to learn languages with *succinct* DFAs or REs. But even though every DFA has an equivalent RE and vice versa, the conversion may require exponential blowups.
October 8, 2025 at 2:37 PM
The important point is that when we say DFAs or REs are easy or hard to learn, we mean that it is easy or hard to learn languages with *succinct* DFAs or REs. But even though every DFA has an equivalent RE and vice versa, the conversion may require exponential blowups.
Number one job: keep them alive, the rest is a bonus
December 9, 2024 at 4:31 AM
Number one job: keep them alive, the rest is a bonus
How about the "set of all CS researcher sets that don't contain themselves"
November 25, 2024 at 4:21 PM
How about the "set of all CS researcher sets that don't contain themselves"
Can you please add me?
November 23, 2024 at 8:10 PM
Can you please add me?
Thanks, I don't feel grumpy enough
November 22, 2024 at 7:46 PM
Thanks, I don't feel grumpy enough