Research
I am interested in the cost of computation: how many queries, cycles or nanoseconds a problem really needs, and how to prove it. So far this has meant quantum query complexity and the security of open hardware.
Papers
Quantum Query Complexity of Minimum Weight Cycles
Naman Goyal · Preprint, 2026
Abstract
We study the minimum weight cycle problem (MWC) and the minimum weight triangle problem (MWT) in the quantum query model, for n-vertex graphs with integer edge weights in [M] given by their adjacency matrix. Roditty and Vassilevska Williams showed that the two problems are classically equivalent. We show that an exact minimum weight cycle of an undirected graph can be found with Õ(n19/12) queries, while Ω(n3/2) queries are necessary. The algorithm learns only the n7/6 lightest vertex pairs, uses quantum counting to locate weight thresholds above them, applies a strict form of the Moore bound to bound the optimum and the size of each weight class, and searches the classes for the few heavy edges of an optimal cycle with nested quantum walks. A simpler version gives Õ(n5/3) queries, and searching for fewer heavy edges trades queries for approximation, with a 2-approximation in Õ(n8/5) queries and a tight O(log n)-approximation in Õ(n3/2) queries. In contrast, MWT costs O(n9/7 log M) queries, so the classical equivalence becomes a polynomial separation. For cycles of constant length we give explicit exponents, such as Õ(n125/83) for the minimum weight 5-cycle, and we prove that deciding whether a graph has a k-cycle of total weight exactly zero requires Ω(n2−2/(⌊k/2⌋+1)) queries for every constant k ≥ 4. Finally, non-adaptive learning graphs cannot beat n2 for cycles of about log n edges, and we conjecture that exact MWC on directed graphs requires n2−o(1) queries.
Projects
Quantum Complexity of Minimum Weight Cycles and TrianglesPreprint
2026 – presentUndergraduate Researcher·IIT Delhi
Roditty and Vassilevska Williams showed that finding a minimum weight cycle in a weighted graph is classically equivalent to finding a minimum weight triangle. This project asks what the two problems cost in the quantum query model, and whether the equivalence survives there. It does not: the two problems separate polynomially.
- Gave an algorithm that finds an exact minimum weight cycle of an undirected graph with Õ(n19/12) queries, against a lower bound of Ω(n3/2).
- Showed that minimum weight triangle needs only O(n9/7 log M) queries, so the classical equivalence becomes a polynomial separation.
- Gave approximation trade-offs, including a 2-approximation in Õ(n8/5) queries and a tight O(log n)-approximation in Õ(n3/2) queries.
- Proved that detecting a zero-weight k-cycle needs Ω(n2−2/(⌊k/2⌋+1)) queries for every constant k ≥ 4.
A Measurement Study of Open-Source RISC-V Processor SecurityPaper in preparation
May – Jul 2026Research Intern·CISPA Helmholtz Center for Information Security, Trusted Systems Group
Open-source RISC-V cores are now shipping in real products, but there has been no systematic look at how well their security claims hold up. This study graded 131 open-source cores on what their code, tests and history actually show, not on what their documentation says.
- Audited all 131 cores by hand, reading the RTL, testbenches and commit history of each.
- Designed the taxonomy used for grading, with 13 dimensions and 50 attributes covering reproducibility, verification and CI/CD resilience.
- Wrote the reproducible Python analysis pipeline and its inter-rater reliability module, which produce 50+ figures and two composite hardware-security indices.
- Found that 95% of the cores have no side-channel defenses and 77% have no secure boot.