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/
What is the computational complexity of learning regular expressions (REs)? At first glance, one might assume this question has long been settled. Yet surprisingly, it does not follow from any known results on learning DFAs or NFAs...
October 8, 2025 at 2:37 PM
What is the computational complexity of learning regular expressions (REs)? At first glance, one might assume this question has long been settled. Yet surprisingly, it does not follow from any known results on learning DFAs or NFAs...
Really nice lecture notes by Alkis Kalavasis: Stability in Machine Learning: Generalization, Privacy & Replicability.
alkisk.github.io
alkisk.github.io
Alkis Kalavasis Homepage
alkisk.github.io
March 22, 2025 at 3:59 PM
Really nice lecture notes by Alkis Kalavasis: Stability in Machine Learning: Generalization, Privacy & Replicability.
alkisk.github.io
alkisk.github.io
Reposted by Idan Attias
when my family asks me about the impact of my research
March 4, 2025 at 5:34 PM
when my family asks me about the impact of my research
Reposted by Idan Attias
New paper: Simulating Time With Square-Root Space
people.csail.mit.edu/rrw/time-vs-...
It's still hard for me to believe it myself, but I seem to have shown that TIME[t] is contained in SPACE[sqrt{t log t}].
To appear in STOC. Comments are very welcome!
people.csail.mit.edu/rrw/time-vs-...
It's still hard for me to believe it myself, but I seem to have shown that TIME[t] is contained in SPACE[sqrt{t log t}].
To appear in STOC. Comments are very welcome!
people.csail.mit.edu
February 21, 2025 at 10:19 PM
New paper: Simulating Time With Square-Root Space
people.csail.mit.edu/rrw/time-vs-...
It's still hard for me to believe it myself, but I seem to have shown that TIME[t] is contained in SPACE[sqrt{t log t}].
To appear in STOC. Comments are very welcome!
people.csail.mit.edu/rrw/time-vs-...
It's still hard for me to believe it myself, but I seem to have shown that TIME[t] is contained in SPACE[sqrt{t log t}].
To appear in STOC. Comments are very welcome!
Reposted by Idan Attias
With @adamsmith.xyz and @thejonullman.bsky.social, we have compiled a set of profiles of 29 people in the "foundations of responsible computing" community ("mathematical research in computation and society writ large") who are on the faculty job market.
Link: drive.google.com/file/d/1Hyvg... 1/3
Link: drive.google.com/file/d/1Hyvg... 1/3
December 24, 2024 at 7:50 PM
With @adamsmith.xyz and @thejonullman.bsky.social, we have compiled a set of profiles of 29 people in the "foundations of responsible computing" community ("mathematical research in computation and society writ large") who are on the faculty job market.
Link: drive.google.com/file/d/1Hyvg... 1/3
Link: drive.google.com/file/d/1Hyvg... 1/3
Reposted by Idan Attias
My book is (at last) out, just in time for Christmas!
A blog post to celebrate and present it: francisbach.com/my-book-is-o...
A blog post to celebrate and present it: francisbach.com/my-book-is-o...
December 21, 2024 at 3:23 PM
My book is (at last) out, just in time for Christmas!
A blog post to celebrate and present it: francisbach.com/my-book-is-o...
A blog post to celebrate and present it: francisbach.com/my-book-is-o...
Looks like a cool result with interesting technical ideas
Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis
Xin Lyu, Kunal Talwar
http://arxiv.org/abs/2412.14396
Xin Lyu, Kunal Talwar
http://arxiv.org/abs/2412.14396
![Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis
Xin Lyu, Kunal Talwar
http://arxiv.org/abs/2412.14396
Fingerprinting codes are a crucial tool for proving lower bounds in
differential privacy. They have been used to prove tight lower bounds for
several fundamental questions, especially in the ``low accuracy'' regime.
Unlike reconstruction/discrepancy approaches however, they are more suited for
query sets that arise naturally from the fingerprinting codes construction. In
this work, we propose a general framework for proving fingerprinting type lower
bounds, that allows us to tailor the technique to the geometry of the query
set. Our approach allows us to prove several new results, including the
following.
First, we show that any (sample- and population-)accurate algorithm for
answering $Q$ arbitrary adaptive counting queries over a universe $\mathcal{X}$
to accuracy $\alpha$ needs $\Omega(\frac{\sqrt{\log |\mathcal{X}|}\cdot \log
Q}{\alpha^3})$ samples, matching known upper bounds. This shows that the
approaches based on differential privacy are optimal for this question, and
improves significantly on the previously known lower bounds of $\frac{\log
Q}{\alpha^2}$ and $\min(\sqrt{Q}, \sqrt{\log |\mathcal{X}|})/\alpha^2$.
Second, we show that any $(\varepsilon,\delta)$-DP algorithm for answering
$Q$ counting queries to accuracy $\alpha$ needs $\Omega(\frac{\sqrt{
\log|\mathcal{X}| \log(1/\delta)} \log Q}{\varepsilon\alpha^2})$ samples,
matching known upper bounds up to constants. Our framework allows for proving
this bound via a direct correlation analysis and improves the prior bound of
[BUV'14] by $\sqrt{\log(1/\delta)}$.
Third, we characterize the sample complexity of answering a set of random
$0$-$1$ queries under approximate differential privacy. We give new upper and
lower bounds in different regimes. By combining them with known results, we can
complete the whole picture.](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:bvdt4psvley2chbqednjkkw2/bafkreid2356j5wj5zbfeujzgozylac2ezqeheoflwu5unvob27nsbwigke@jpeg)
December 20, 2024 at 3:30 PM
Looks like a cool result with interesting technical ideas
Reposted by Idan Attias
I'm excited about a new paper that gives tractable generalizations of Aumann's Agreement Theorem, with an eye towards human/model collaboration in machine learning. We can implement algorithms that can "converse" with people and quickly come to agreement on downstream actions. 🧵
December 2, 2024 at 5:12 PM
I'm excited about a new paper that gives tractable generalizations of Aumann's Agreement Theorem, with an eye towards human/model collaboration in machine learning. We can implement algorithms that can "converse" with people and quickly come to agreement on downstream actions. 🧵
So many starter packs... someone needs to create the "set of all CS researcher sets that don't contain themselves"
November 25, 2024 at 4:01 PM
So many starter packs... someone needs to create the "set of all CS researcher sets that don't contain themselves"
Reposted by Idan Attias
I made a starter pack for learning theory people to gather some people around the topic. There are too many names on here that I don't know so I only added a few I do. If you believe you should be on this list, let me know. I will add people with accurate profile descriptions.
go.bsky.app/21nFz12
go.bsky.app/21nFz12
November 10, 2024 at 6:08 PM
I made a starter pack for learning theory people to gather some people around the topic. There are too many names on here that I don't know so I only added a few I do. If you believe you should be on this list, let me know. I will add people with accurate profile descriptions.
go.bsky.app/21nFz12
go.bsky.app/21nFz12