Venkatesan Guruswami
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Venkatesan Guruswami has a total of 127 co-authors. Here are the top co-authors by number of shared publications:
- Chaoping Xing
Shanghai Jiao Tong University
10 shared publications - Ali Kemal Sinop
Simons Institute for the Theory of Computing University of California at Berkeley
7 shared publications - Ray Li
Santa Clara University, Santa Clara, USA
7 shared publications - Euiwoong Lee
University of Michigan, Ann Arbor, MI 48105 USA
5 shared publications - Joshua Brakensiek
Department of Computer Science Stanford University Stanford CA
4 shared publications Vijay Bhattiprolu
Carnegie Mellon University
4 shared publications
Latest Publications
- Open Access
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 486-489
Brief Announcement: Scheduling Problems with Constrained Rejections
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 486-489
Open AccessBrief Announcement: Scheduling Problems with Constrained Rejections
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1558-1568
Optimal Proximity Gaps for Subspace-Design Codes and (Random) Reed-Solomon Codes
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1558-1568
Open AccessOptimal Proximity Gaps for Subspace-Design Codes and (Random) Reed-Solomon Codes
- Open Access
- 4 May 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 18 (2) , 1-15
Hardness of Learning Boolean Functions from Label Proportions
In recent years, the framework of learning from label proportions (LLP) has been gaining importance in machine learning. In this setting, the training examples are aggregated into subsets or bags and only the average label per bag is available for learning an example-level predictor. This generalizes traditional PAC learning which is the special case of unit-sized bags. The computational learning aspects of LLP were studied in recent works [ 22 , 23 ] which showed algorithms and hardness for learning halfspaces in the LLP setting. In this work, we focus on the intractability of LLP learning Boolean functions. Our first result shows that given a collection of bags of size at most 2 which are consistent with an OR function, it is NP-hard to find a CNF of constantly many clauses which satisfies any constant-fraction of the bags. This is in contrast with the work of [ 22 ], which gave a (2/5)-approximation for learning ORs using a halfspace. Thus, our result provides a separation between constant clause CNFs and halfspaces as hypotheses for LLP learning ORs. Next, we prove the hardness of satisfying more than 1/2 + o (1) fraction of such bags using a t -DNF (i.e., DNF where each term has ≤ t literals) for any constant t . In usual PAC learning, such a hardness was known [ 16 ] only for learning noisy ORs. We also study the learnability of parities and show that it is NP-hard to satisfy more than ( q /2 q -1 + o (1))-fraction of q -sized bags which are consistent with a parity using a parity, while a random parity-based algorithm achieves a (1/2 q -2 )-approximation.
- 4 May 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 18 (2) , 1-15
Open AccessHardness of Learning Boolean Functions from Label Proportions
In recent years, the framework of learning from label proportions (LLP) has been gaining importance in machine learning. In this setting, the training examples are aggregated into subsets or bags and only the average label per bag is available for learning an example-level predictor. This generalizes traditional PAC learning which is the special case of unit-sized bags. The computational learning aspects of LLP were studied in recent works [ 22 , 23 ] which showed algorithms and hardness for learning halfspaces in the LLP setting. In this work, we focus on the intractability of LLP learning Boolean functions. Our first result shows that given a collection of bags of size at most 2 which are consistent with an OR function, it is NP-hard to find a CNF of constantly many clauses which satisfies any constant-fraction of the bags. This is in contrast with the work of [ 22 ], which gave a (2/5)-approximation for learning ORs using a halfspace. Thus, our result provides a separation between constant clause CNFs and halfspaces as hypotheses for LLP learning ORs. Next, we prove the hardness of satisfying more than 1/2 + o (1) fraction of such bags using a t -DNF (i.e., DNF where each term has ≤ t literals) for any constant t . In usual PAC learning, such a hardness was known [ 16 ] only for learning noisy ORs. We also study the learnability of parities and show that it is NP-hard to satisfy more than ( q /2 q -1 + o (1))-fraction of q -sized bags which are consistent with a parity using a parity, while a random parity-based algorithm achieves a (1/2 q -2 )-approximation.
- 17 November 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE BITS the Information Theory Magazine
- Vol. PP (26924080) , 1-13
Maximal Recoverability: A Nexus of Coding Theory
In the modern era of large-scale computing systems, a crucial use of error correcting codes is to judiciously introduce redundancy to ensure recoverability from failure. To get the most out of every byte, practitioners and theorists have introduced the framework of maximal recoverability (MR) to study optimal error-correcting codes in various architectures. In this survey, we dive into the study of two families of MR codes: MR locally recoverable codes (LRCs) (also known as partial MDS codes) and grid codes (GCs). For both families of codes, we discuss the primary recoverability guarantees of each class of codes as well as what is known concerning optimal constructions of each class of codes. Along the way, we discuss many surprising connections between MR codes and broader questions in computer science and mathematics. For MR LRCs, the use of skew polynomial codes has unified many previous constructions. For MR GCs, the theory of higher order MDS codes shows that MR GCs can be used to construct optimal list-decodable codes. Furthermore, the optimally recoverable patterns of MR GCs have close ties to long-standing problems on the structural rigidity of graphs.
- 17 November 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE BITS the Information Theory Magazine
- Vol. PP (26924080) , 1-13
Maximal Recoverability: A Nexus of Coding Theory
In the modern era of large-scale computing systems, a crucial use of error correcting codes is to judiciously introduce redundancy to ensure recoverability from failure. To get the most out of every byte, practitioners and theorists have introduced the framework of maximal recoverability (MR) to study optimal error-correcting codes in various architectures. In this survey, we dive into the study of two families of MR codes: MR locally recoverable codes (LRCs) (also known as partial MDS codes) and grid codes (GCs). For both families of codes, we discuss the primary recoverability guarantees of each class of codes as well as what is known concerning optimal constructions of each class of codes. Along the way, we discuss many surprising connections between MR codes and broader questions in computer science and mathematics. For MR LRCs, the use of skew polynomial codes has unified many previous constructions. For MR GCs, the theory of higher order MDS codes shows that MR GCs can be used to construct optimal list-decodable codes. Furthermore, the optimally recoverable patterns of MR GCs have close ties to long-standing problems on the structural rigidity of graphs.
- Open Access
- 9 October 2025
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 72 (5) , 1-40
Parameterized Inapproximability Hypothesis under ETH
The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the number of variables, from one where every assignment fails to satisfy an ɛ fraction of constraints for some absolute constant ɛ > 0. PIH plays the role of the PCP theorem in parameterized complexity. However, PIH has only been established under the Gap Exponential Time Hypothesis (ETH), a very strong assumption with an inherent gap. In this work, we prove PIH under the ETH. This is the first proof of PIH from a gap-free assumption. Our proof is self-contained and elementary. We identify an ETH-hard CSP whose variables take vector values, and constraints are either linear or of a special parallel structure. Both kinds of constraints can be checked with constant soundness via a “parallel PCP of proximity” based on the Walsh-Hadamard code.
- 9 October 2025
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 72 (5) , 1-40
Open AccessParameterized Inapproximability Hypothesis under ETH
The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the number of variables, from one where every assignment fails to satisfy an ɛ fraction of constraints for some absolute constant ɛ > 0. PIH plays the role of the PCP theorem in parameterized complexity. However, PIH has only been established under the Gap Exponential Time Hypothesis (ETH), a very strong assumption with an inherent gap. In this work, we prove PIH under the ETH. This is the first proof of PIH from a gap-free assumption. Our proof is self-contained and elementary. We identify an ETH-hard CSP whose variables take vector values, and constraints are either linear or of a special parallel structure. Both kinds of constraints can be checked with constant soundness via a “parallel PCP of proximity” based on the Walsh-Hadamard code.
- 16 September 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Information Theory
- Vol. 6, 383-393
Geno-Weaving: A Framework for Low-Complexity Capacity-Achieving DNA Data Storage
As a potential implementation of data storage using DNA molecules, multiple strands of DNA are stored unordered in a liquid container. When the data are needed, an array of DNA readers will sample the strands with replacement, producing a Poisson-distributed number of noisy reads for each strand. The primary challenge here is to design an algorithm that reconstructs data from these unsorted, repetitive, and noisy reads. In this paper, we lay down a capacity-achieving rateless code along each strand to encode its index; we then lay down a capacity-achieving block code at the same position across all strands to protect the data. These codes weave a low-complexity storage scheme that saturates the fundamental upper limit of DNA. This improves upon the previous work of Weinberger and Merhav, which proves said bound and uses high-complexity random codes to saturate the limit. Our scheme also differs from other concatenation-based implementations of DNA data storage in the sense that, instead of decoding the inner codes first and passing the results to the outer code, our decoder alternates between the rateless codes and the block codes.
- 16 September 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Information Theory
- Vol. 6, 383-393
Geno-Weaving: A Framework for Low-Complexity Capacity-Achieving DNA Data Storage
As a potential implementation of data storage using DNA molecules, multiple strands of DNA are stored unordered in a liquid container. When the data are needed, an array of DNA readers will sample the strands with replacement, producing a Poisson-distributed number of noisy reads for each strand. The primary challenge here is to design an algorithm that reconstructs data from these unsorted, repetitive, and noisy reads. In this paper, we lay down a capacity-achieving rateless code along each strand to encode its index; we then lay down a capacity-achieving block code at the same position across all strands to protect the data. These codes weave a low-complexity storage scheme that saturates the fundamental upper limit of DNA. This improves upon the previous work of Weinberger and Merhav, which proves said bound and uses high-complexity random codes to saturate the limit. Our scheme also differs from other concatenation-based implementations of DNA data storage in the sense that, instead of decoding the inner codes first and passing the results to the outer code, our decoder alternates between the rateless codes and the block codes.
- Open Access
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 2136-2144
Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 2136-2144
Open AccessAlmost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
- Open Access
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 707-717
Asymptotically Good Quantum Codes with Transversal Non-Clifford Gates
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 707-717
Open AccessAsymptotically Good Quantum Codes with Transversal Non-Clifford Gates
- Open Access
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 1614-1625
Redundancy Is All You Need
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 1614-1625
Open AccessRedundancy Is All You Need