Akbar Rafiey
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Akbar Rafiey has a total of 12 co-authors. Here are the top co-authors by number of shared publications:
- Arash Rafiey
Indiana State University
2 shared publications - Andrei Bulatov
School of Computer Science, Simon Fraser University
1 shared publication - Bahar Salamatian
Qualcomm, Vancouver, Canada
1 shared publication - Gal Mishne
Halicioğlu Data Science Institute, UC San Diego, La Jolla, CA 92093 USA
1 shared publication - Jeff Kinne
Indiana State University
1 shared publication - Jesse He
Halıcıoğlu Data Science Institute, University of California, San Diego, San Diego, California, USA
1 shared publication
Latest Publications
- Open Access
- 4 May 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 18 (2) , 1-34
The Ideal Membership Problem and Abelian Groups
Given polynomials f 0 , f 1 , …, f k the Ideal Membership Problem, IMP for short, asks if f 0 belongs to the ideal generated by f 1 , …, f k . In the search version of this problem, the task is to find a proof of this fact. The IMP is a well-known fundamental problem with numerous applications. For instance, it underlies many proof systems based on polynomials such as Nullstellensatz, Polynomial Calculus, and Sum-of-Squares. Although the IMP is in general intractable, in many important cases it can be efficiently solved. Mastrolilli [SODA’19] initiated a systematic study of IMPs for ideals arising from Constraint Satisfaction Problems (CSPs), parameterized by constraint languages, denoted IMP(Γ). The ultimate goal of this line of research is to classify all such IMPs accordingly to their complexity. Mastrolilli achieved this goal for IMPs arising from CSP(Γ) where Γ is a Boolean constraint language, while Bulatov and Rafiey [STOC’22] advanced these results to several cases of CSPs over finite domains. In this article, we consider IMPs arising from CSPs over “affine” constraint languages, in which constraints are subgroups (or their cosets) of direct products of Abelian groups. This kind of CSPs include systems of linear equations and are considered one of the most important types of tractable CSPs. Some special cases of the problem have been considered before by Bharathi and Mastrolilli [MFCS’21] for linear equations modulo 2, and by Bulatov and Rafiey [STOC’22] for systems of linear equations over GF ( p ), p prime. Here, we prove that if Γ is an affine constraint language then IMP(Γ) is solvable in polynomial time assuming the input polynomial has bounded degree.
- 4 May 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 18 (2) , 1-34
Open AccessThe Ideal Membership Problem and Abelian Groups
Given polynomials f 0 , f 1 , …, f k the Ideal Membership Problem, IMP for short, asks if f 0 belongs to the ideal generated by f 1 , …, f k . In the search version of this problem, the task is to find a proof of this fact. The IMP is a well-known fundamental problem with numerous applications. For instance, it underlies many proof systems based on polynomials such as Nullstellensatz, Polynomial Calculus, and Sum-of-Squares. Although the IMP is in general intractable, in many important cases it can be efficiently solved. Mastrolilli [SODA’19] initiated a systematic study of IMPs for ideals arising from Constraint Satisfaction Problems (CSPs), parameterized by constraint languages, denoted IMP(Γ). The ultimate goal of this line of research is to classify all such IMPs accordingly to their complexity. Mastrolilli achieved this goal for IMPs arising from CSP(Γ) where Γ is a Boolean constraint language, while Bulatov and Rafiey [STOC’22] advanced these results to several cases of CSPs over finite domains. In this article, we consider IMPs arising from CSPs over “affine” constraint languages, in which constraints are subgroups (or their cosets) of direct products of Abelian groups. This kind of CSPs include systems of linear equations and are considered one of the most important types of tractable CSPs. Some special cases of the problem have been considered before by Bharathi and Mastrolilli [MFCS’21] for linear equations modulo 2, and by Bulatov and Rafiey [STOC’22] for systems of linear equations over GF ( p ), p prime. Here, we prove that if Γ is an affine constraint language then IMP(Γ) is solvable in polynomial time assuming the input polynomial has bounded degree.
- Open Access
- 3 August 2025
- Published by Association for Computing Machinery (ACM)
- p. 884-895
Explaining GNN Explanations with Edge Gradients
- 3 August 2025
- Published by Association for Computing Machinery (ACM)
- p. 884-895
Open AccessExplaining GNN Explanations with Edge Gradients
- 6 March 2024
- Published by Springer Nature
- p. 31-45
Bi-arc Digraphs: Recognition Algorithm and Applications
- 6 March 2024
- Published by Springer Nature
- p. 31-45
Bi-arc Digraphs: Recognition Algorithm and Applications
- Open Access
- 31 August 2023
- Published by Society for Privacy and Confidentiality Research in Journal of Privacy and Confidentiality
- Vol. 13 (1)
Private Boosted Decision Trees via Smooth Re-Weighting
Protecting the privacy of people whose data is used by machine learning algorithms is important. Differential Privacy is the appropriate mathematical framework for formal guarantees of privacy, and boosted decision trees are a popular machine learning technique. So we propose and test a practical algorithm for boosting decision trees that guarantees differential privacy. Privacy is enforced because our booster never puts too much weight on any one example; this ensures that each individual's data never influences a single tree "too much." Experiments show that this boosting algorithm can produce better model sparsity and accuracy than other differentially private ensemble classifiers.
- 31 August 2023
- Published by Society for Privacy and Confidentiality Research in Journal of Privacy and Confidentiality
- Vol. 13 (1)
Open AccessPrivate Boosted Decision Trees via Smooth Re-Weighting
Protecting the privacy of people whose data is used by machine learning algorithms is important. Differential Privacy is the appropriate mathematical framework for formal guarantees of privacy, and boosted decision trees are a popular machine learning technique. So we propose and test a practical algorithm for boosting decision trees that guarantees differential privacy. Privacy is enforced because our booster never puts too much weight on any one example; this ensures that each individual's data never influences a single tree "too much." Experiments show that this boosting algorithm can produce better model sparsity and accuracy than other differentially private ensemble classifiers.