Abhiram Aravind

dblp:428/9329 · DBLP profile ↗
← Back
1ranked-venue papers
1as first author
1since 2021 · last 2026
0009-0000-1820-3357ORCID · reported

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 1 · 1 first-author · 1 since 2021

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Theoretical computer science
1 paper
Computational complexity · 67% Algorithms and data structures · 33%

Topics — the 3 heaviest of 3, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Algorithms and data structures
learning algorithms
1.012026
Learning Read-Once Determinants and the Principal Minor Assignment Problem · STOC 2026
Computational complexity › algebraic complexity
polynomial identity testing
1.012026
Learning Read-Once Determinants and the Principal Minor Assignment Problem · STOC 2026
Computational complexity › learning theory
proper learning
1.012026
Learning Read-Once Determinants and the Principal Minor Assignment Problem · STOC 2026

Methods — techniques the papers use, named apart from their topics

randomized algorithm · 1.0derandomization · 1.0
YearPublicationVenuePosition
2026 Learning Read-Once Determinants and the Principal Minor Assignment Problem
abstract
A symbolic determinant under rank-one restriction computes a polynomial of the form det(A0 + A1y1 + … + Anyn), where A0, A1, …, An are square matrices over a field F and rank(Ai) = 1 for each i ∈ [n]. This class of polynomials has been studied extensively, since the work of Edmonds (1967), in the context of linear matroids, matching, matrix completion and polynomial identity testing. We study the following learning problem for this class: Given black-box access to an n-variate polynomial f = det(A0 + A1y1 + … + Anyn), where A0, A1, …, An are unknown square matrices over F and rank(Ai) = 1 for each i ∈ [n], find a square matrix B0 and rank-one square matrices B1, …, Bn over F such that f = det(B0 + B1y1 + … + Bnyn). In this work, we give a randomized poly(n) time algorithm to solve this problem; the algorithm can be derandomized in quasi-polynomial time. To our knowledge, this is the first efficient learning algorithm for this class. As the above-mentioned class is known to be equivalent to the class of read-once determinants (RODs), we will refer to the problem as learning RODs. An ROD computes the determinant of a matrix whose entries are field constants or variables and every variable appears at most once in the matrix. Thus, the class of RODs is a rare example of a well-studied class of polynomials that admits efficient proper learning.
Abhiram Aravind, Abhranil Chatterjee 0001, Sumanta Ghosh, Rohit Gurjar, Roshan Raj, Chandan Saha 0001
STOC1