DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.97

Quantum Algorithms on Edge Lists: Hiding, Shuffling, and Cycle Finding

Authors: Amin Shiraz Gilani, Daochen Wang, Pei Wu, and Xingyu Zhou

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

The edge list model is arguably the simplest input model for graphs, where the graph is specified by a list of its edges. In this model, we study the quantum query complexity of three variants of the triangle finding problem. The first asks whether there exists a triangle containing a target edge and raises general questions about the hiding of a problem’s input among irrelevant data. The second asks whether there exists a triangle containing a target vertex and raises general questions about the shuffling of a problem’s input. The third asks whether there exists a triangle; this problem bridges the 3-distinctness and 3-sum problems, which have been extensively studied by both cryptographers and complexity theorists. We provide tight or nearly tight results for these problems as well as some first answers to the general questions they raise. Furthermore, given any graph with low maximum degree, such as a typical random sparse graph, we prove that the quantum query complexity of finding a length-k cycle in its length-m edge list is m^{3/4-1/(2^{k+2}-4) ± o(1)}, which matches the best-known upper bound for the quantum query complexity of k-distinctness on length-m inputs up to an m^o(1) factor. We prove the lower bound by developing new techniques within Zhandry’s recording query framework [Zhandry, 2019] as generalized by Hamoudi and Magniez [Hamoudi and Magniez, 2023]. These techniques extend the framework to treat any non-product distribution that results from conditioning a product distribution on the absence of rare events. We prove the upper bound by adapting Belovs’s learning graph algorithm for k-distinctness [Belovs, 2012]. Finally, assuming a plausible conjecture concerning only cycle finding, we show that the lower bound can be lifted to an essentially tight lower bound on the quantum query complexity of k-distinctness, which is a long-standing open question.

Cite as

Amin Shiraz Gilani, Daochen Wang, Pei Wu, and Xingyu Zhou. Quantum Algorithms on Edge Lists: Hiding, Shuffling, and Cycle Finding. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 97:1-97:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gilani_et_al:LIPIcs.ICALP.2026.97,
  author =	{Gilani, Amin Shiraz and Wang, Daochen and Wu, Pei and Zhou, Xingyu},
  title =	{{Quantum Algorithms on Edge Lists: Hiding, Shuffling, and Cycle Finding}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{97:1--97:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.97},
  URN =		{urn:nbn:de:0030-drops-264867},
  doi =		{10.4230/LIPIcs.ICALP.2026.97},
  annote =	{Keywords: Quantum query complexity, graph algorithms, edge list model}
}

Document

DOI: 10.4230/LIPIcs.FORC.2025.9

Optimal Rates for Robust Stochastic Convex Optimization

Authors: Changyu Gao, Andrew Lowy, Xingyu Zhou, and Stephen J. Wright

Published in: LIPIcs, Volume 329, 6th Symposium on Foundations of Responsible Computing (FORC 2025)

Abstract

Machine learning algorithms in high-dimensional settings are highly susceptible to the influence of even a small fraction of structured outliers, making robust optimization techniques essential. In particular, within the ε-contamination model, where an adversary can inspect and replace up to an ε-fraction of the samples, a fundamental open problem is determining the optimal rates for robust stochastic convex optimization (SCO) under such contamination. We develop novel algorithms that achieve minimax-optimal excess risk (up to logarithmic factors) under the ε-contamination model. Our approach improves over existing algorithms, which are not only suboptimal but also require stringent assumptions, including Lipschitz continuity and smoothness of individual sample functions. By contrast, our optimal algorithms do not require these stringent assumptions, assuming only population-level smoothness of the loss. Moreover, our algorithms can be adapted to handle the case in which the covariance parameter is unknown, and can be extended to nonsmooth population risks via convolutional smoothing. We complement our algorithmic developments with a tight information-theoretic lower bound for robust SCO.

Cite as

Changyu Gao, Andrew Lowy, Xingyu Zhou, and Stephen J. Wright. Optimal Rates for Robust Stochastic Convex Optimization. In 6th Symposium on Foundations of Responsible Computing (FORC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 329, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gao_et_al:LIPIcs.FORC.2025.9,
  author =	{Gao, Changyu and Lowy, Andrew and Zhou, Xingyu and Wright, Stephen J.},
  title =	{{Optimal Rates for Robust Stochastic Convex Optimization}},
  booktitle =	{6th Symposium on Foundations of Responsible Computing (FORC 2025)},
  pages =	{9:1--9:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-367-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{329},
  editor =	{Bun, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2025.9},
  URN =		{urn:nbn:de:0030-drops-231369},
  doi =		{10.4230/LIPIcs.FORC.2025.9},
  annote =	{Keywords: Adversarial Robustness, Machine Learning, Optimization Algorithms, Robust Optimization, Stochastic Convex Optimization}
}

Search Results

Documents authored by Zhou, Xingyu

Quantum Algorithms on Edge Lists: Hiding, Shuffling, and Cycle Finding

Abstract

Cite as

Optimal Rates for Robust Stochastic Convex Optimization

Abstract

Cite as

Thanks for your feedback!

Could not send message