Aleksandros Sobczyk
@asobczyk.bsky.social
Pinned
Aleksandros Sobczyk
@asobczyk.bsky.social
· Apr 14
Deterministic complexity analysis of Hermitian eigenproblems
In this work we revisit the arithmetic and bit complexity of Hermitian eigenproblems. We first provide an analysis for the divide-and-conquer tridiagonal eigensolver of Gu and Eisenstat [GE95] in the ...
arxiv.org
With my first Bluesky post, I am very pleased to share that my last PhD paper "Deterministic complexity analysis of Hermitian eigenproblems" has been accepted in ICALP 2025. A preprint is available on Arxiv:
arxiv.org/abs/2410.21550
A bit more info on linkedin: www.linkedin.com/posts/aleksa...
arxiv.org/abs/2410.21550
A bit more info on linkedin: www.linkedin.com/posts/aleksa...
@jannisblrn.bsky.social wrote a very nice teaser about our Neurips paper Quantum Doubly Stochastic Transformers (spotlight). Our co-authors Filip and Kahn will present it in San Diego, and Jannis in EurIPS. You can find links to the paper, video, and poster below:
www.linkedin.com/posts/jannis...
www.linkedin.com/posts/jannis...
#transformers #neurips #eurips #ibmresearch | Jannis Born
𝗡𝗲𝘂𝗿𝗜𝗣𝗦 𝘀𝗽𝗼𝘁𝗹𝗶𝗴𝗵𝘁 for our work on "𝗤𝘂𝗮𝗻𝘁𝘂𝗺 𝗗𝗼𝘂𝗯𝗹𝘆 𝗦𝘁𝗼𝗰𝗵𝗮𝘀𝘁𝗶𝗰 𝗧𝗿𝗮𝗻𝘀𝗳𝗼𝗿𝗺𝗲𝗿𝘀" 🔦
𝘊𝘢𝘯 𝘱𝘳𝘪𝘯𝘤𝘪𝘱𝘭𝘦𝘴 𝘧𝘳𝘰𝘮 𝘲𝘶𝘢𝘯𝘵𝘶𝘮 𝘤𝘰𝘮𝘱𝘶𝘵𝘪𝘯𝘨 𝘣𝘦 𝘣𝘭𝘦𝘯𝘥𝘦𝘥 𝘪𝘯𝘵𝘰 𝘵𝘩𝘦 𝘮𝘰𝘴𝘵 𝘱𝘰𝘸𝘦𝘳𝘧𝘶𝘭 𝘔𝘓 𝘮𝘰𝘥𝘦𝘭𝘴? 🤔
𝗧𝗵𝗲 𝗽𝗿𝗼𝗯𝗹𝗲𝗺 𝗶𝗻 #𝗧𝗿𝗮𝗻𝘀𝗳𝗼𝗿𝗺𝗲𝗿𝘀: Transf...
www.linkedin.com
November 14, 2025 at 7:34 AM
@jannisblrn.bsky.social wrote a very nice teaser about our Neurips paper Quantum Doubly Stochastic Transformers (spotlight). Our co-authors Filip and Kahn will present it in San Diego, and Jannis in EurIPS. You can find links to the paper, video, and poster below:
www.linkedin.com/posts/jannis...
www.linkedin.com/posts/jannis...
Reposted by Aleksandros Sobczyk
CS at Aarhus University is hiring up to six professors of any rank and area! Come join my section and do cutting-edge research in TCS, database systems and/or ML/AI, both from a theory and applied side.
international.au.dk/about/profil...
The application deadline is January 5th, 2026.
international.au.dk/about/profil...
The application deadline is January 5th, 2026.
Aarhus University is hiring Assistant, Associate and Full Professors for the Department of Computer Science - Vacancy at Aarhus University
Vacancy at Computer Science, Dept. of, Aarhus University
international.au.dk
October 21, 2025 at 6:08 AM
CS at Aarhus University is hiring up to six professors of any rank and area! Come join my section and do cutting-edge research in TCS, database systems and/or ML/AI, both from a theory and applied side.
international.au.dk/about/profil...
The application deadline is January 5th, 2026.
international.au.dk/about/profil...
The application deadline is January 5th, 2026.
Reposted by Aleksandros Sobczyk
On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach
Link to the paper: arxiv.org/abs/2510.04115
Link to the paper: arxiv.org/abs/2510.04115
October 18, 2025 at 9:38 PM
On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach
Link to the paper: arxiv.org/abs/2510.04115
Link to the paper: arxiv.org/abs/2510.04115
Reposted by Aleksandros Sobczyk
New paper out with Chris Camaño, Raphael Meyer, and Joel Tropp re-examining sketching algorithms! Included: subspace injections as an alternative to subspace embeddings, the theory and practice of sparse sketching, tensor sketching, and much more! arxiv.org/abs/2508.21189
Faster Linear Algebra Algorithms with Structured Random Matrices
To achieve the greatest possible speed, practitioners regularly implement randomized algorithms for low-rank approximation and least-squares regression with structured dimension reduction maps. Despit...
arxiv.org
September 3, 2025 at 5:42 PM
New paper out with Chris Camaño, Raphael Meyer, and Joel Tropp re-examining sketching algorithms! Included: subspace injections as an alternative to subspace embeddings, the theory and practice of sparse sketching, tensor sketching, and much more! arxiv.org/abs/2508.21189
We have a new preprint with Almudena Carrera Vazquez, one of the last (and favorite) works that I contributed to before leaving IBM. Arxiv link:
arxiv.org/abs/2508.21002
The paper is about quantum algorithms for approximating so-called "spectral gaps" between consecutive pairs of eigenvalues.
arxiv.org/abs/2508.21002
The paper is about quantum algorithms for approximating so-called "spectral gaps" between consecutive pairs of eigenvalues.
Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation
Approximating the $k$-th spectral gap $Δ_k=|λ_k-λ_{k+1}|$ and the corresponding midpoint $μ_k=\frac{λ_k+λ_{k+1}}{2}$ of an $N\times N$ Hermitian matrix with eigenvalues $λ_1\geqλ_2\geq\ldots\geqλ_N$, ...
arxiv.org
August 31, 2025 at 9:19 AM
We have a new preprint with Almudena Carrera Vazquez, one of the last (and favorite) works that I contributed to before leaving IBM. Arxiv link:
arxiv.org/abs/2508.21002
The paper is about quantum algorithms for approximating so-called "spectral gaps" between consecutive pairs of eigenvalues.
arxiv.org/abs/2508.21002
The paper is about quantum algorithms for approximating so-called "spectral gaps" between consecutive pairs of eigenvalues.
We have couple of new works to share:
1) arxiv.org/abs/2506.23906
with Giuseppe Sorentino & Anastasios Zouzias,
2) arxiv.org/abs/2506.10854
with Pál András Papp & Albert-Jan Yzelman, to appear in SPAA '25.
From tomorrow I'll be in Aarhus for ICALP until 11/7, ping me if you want to chat!
1) arxiv.org/abs/2506.23906
with Giuseppe Sorentino & Anastasios Zouzias,
2) arxiv.org/abs/2506.10854
with Pál András Papp & Albert-Jan Yzelman, to appear in SPAA '25.
From tomorrow I'll be in Aarhus for ICALP until 11/7, ping me if you want to chat!
Segmented Operations using Matrix Multiplications
Specialized computational units that perform small matrix multiplications as primitive operations are typically present in modern accelerators. However, these units are often underutilized for many fu...
arxiv.org
July 6, 2025 at 10:55 AM
We have couple of new works to share:
1) arxiv.org/abs/2506.23906
with Giuseppe Sorentino & Anastasios Zouzias,
2) arxiv.org/abs/2506.10854
with Pál András Papp & Albert-Jan Yzelman, to appear in SPAA '25.
From tomorrow I'll be in Aarhus for ICALP until 11/7, ping me if you want to chat!
1) arxiv.org/abs/2506.23906
with Giuseppe Sorentino & Anastasios Zouzias,
2) arxiv.org/abs/2506.10854
with Pál András Papp & Albert-Jan Yzelman, to appear in SPAA '25.
From tomorrow I'll be in Aarhus for ICALP until 11/7, ping me if you want to chat!
Anyone have an idea how accurate are the Google scholar metrics? The following highly-cited paper seems to be missing from the metrics of *both* STOC and JACM:
dl.acm.org/doi/abs/10.1...
dl.acm.org/doi/abs/10.1...
Low-Rank Approximation and Regression in Input Sparsity Time | Journal of the ACM
We design a new distribution over m × n matrices S so that, for any fixed n × d matrix A of rank r, with probability at least 9/10, ∥SAx∥2 = (1 ± ε)∥Ax∥2 simultaneously for all x ∈ Rd. Here, m is boun...
dl.acm.org
June 19, 2025 at 8:40 PM
Anyone have an idea how accurate are the Google scholar metrics? The following highly-cited paper seems to be missing from the metrics of *both* STOC and JACM:
dl.acm.org/doi/abs/10.1...
dl.acm.org/doi/abs/10.1...
Reposted by Aleksandros Sobczyk
New paper: Learning to Add, Multiply, and Execute Algorithmic Instructions Exactly with Neural Networks
May 26, 2025 at 3:21 AM
New paper: Learning to Add, Multiply, and Execute Algorithmic Instructions Exactly with Neural Networks
Reposted by Aleksandros Sobczyk
I have an opening for a post doc position in machine learning theory, with a deadline of June 1st. Please share and apply: international.au.dk/about/profil...
Post doc position in theory of machine learning at Department of Computer Science, Aarhus University - Vacancy at Aarhus University
Vacancy at Computer Science, Dept. of, Aarhus University
international.au.dk
April 30, 2025 at 9:24 AM
I have an opening for a post doc position in machine learning theory, with a deadline of June 1st. Please share and apply: international.au.dk/about/profil...
With my first Bluesky post, I am very pleased to share that my last PhD paper "Deterministic complexity analysis of Hermitian eigenproblems" has been accepted in ICALP 2025. A preprint is available on Arxiv:
arxiv.org/abs/2410.21550
A bit more info on linkedin: www.linkedin.com/posts/aleksa...
arxiv.org/abs/2410.21550
A bit more info on linkedin: www.linkedin.com/posts/aleksa...
Deterministic complexity analysis of Hermitian eigenproblems
In this work we revisit the arithmetic and bit complexity of Hermitian eigenproblems. We first provide an analysis for the divide-and-conquer tridiagonal eigensolver of Gu and Eisenstat [GE95] in the ...
arxiv.org
April 14, 2025 at 5:25 PM
With my first Bluesky post, I am very pleased to share that my last PhD paper "Deterministic complexity analysis of Hermitian eigenproblems" has been accepted in ICALP 2025. A preprint is available on Arxiv:
arxiv.org/abs/2410.21550
A bit more info on linkedin: www.linkedin.com/posts/aleksa...
arxiv.org/abs/2410.21550
A bit more info on linkedin: www.linkedin.com/posts/aleksa...
Reposted by Aleksandros Sobczyk
We're offering a fully funded PhD at the intersection of ML/AI and the natural sciences with a focus on sustainability and chemistry.
You'll work at WUR in the Netherlands, ranked #3 in environ. sciences, #1 in agricultural science, #38 in life sciences (QS).
Apply here:
www.wur.nl/nl/vacature/...
You'll work at WUR in the Netherlands, ranked #3 in environ. sciences, #1 in agricultural science, #38 in life sciences (QS).
Apply here:
www.wur.nl/nl/vacature/...
March 14, 2025 at 5:29 PM
We're offering a fully funded PhD at the intersection of ML/AI and the natural sciences with a focus on sustainability and chemistry.
You'll work at WUR in the Netherlands, ranked #3 in environ. sciences, #1 in agricultural science, #38 in life sciences (QS).
Apply here:
www.wur.nl/nl/vacature/...
You'll work at WUR in the Netherlands, ranked #3 in environ. sciences, #1 in agricultural science, #38 in life sciences (QS).
Apply here:
www.wur.nl/nl/vacature/...