6 Search Results for "Love, Peter J."


Document
Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses

Authors: Chris Jones, Kunal Marwaha, Juspreet Singh Sandhu, and Jonathan Shi

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)


Abstract
We study random constraint satisfaction problems (CSPs) at large clause density. We relate the structure of near-optimal solutions for any Boolean Max-CSP to that for an associated spin glass on the hypercube, using the Guerra-Toninelli interpolation from statistical physics. The noise stability polynomial of the CSP’s predicate is, up to a constant, the mixture polynomial of the associated spin glass. We show two main consequences: 1) We prove that the maximum fraction of constraints that can be satisfied in a random Max-CSP at large clause density is determined by the ground state energy density of the corresponding spin glass. Since the latter value can be computed with the Parisi formula [Parisi, 1980; Talagrand, 2006; Auffinger and Chen, 2017], we provide numerical values for some popular CSPs. 2) We prove that a Max-CSP at large clause density possesses generalized versions of the overlap gap property if and only if the same holds for the corresponding spin glass. We transfer results from [Huang and Sellke, 2021] to obstruct algorithms with overlap concentration on a large class of Max-CSPs. This immediately includes local classical and local quantum algorithms [Chou et al., 2022].

Cite as

Chris Jones, Kunal Marwaha, Juspreet Singh Sandhu, and Jonathan Shi. Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 77:1-77:26, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{jones_et_al:LIPIcs.ITCS.2023.77,
  author =	{Jones, Chris and Marwaha, Kunal and Sandhu, Juspreet Singh and Shi, Jonathan},
  title =	{{Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{77:1--77:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.77},
  URN =		{urn:nbn:de:0030-drops-175804},
  doi =		{10.4230/LIPIcs.ITCS.2023.77},
  annote =	{Keywords: spin glass, overlap gap property, constraint satisfaction problem, Guerra-Toninelli interpolation}
}
Document
The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model

Authors: Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, and Leo Zhou

Published in: LIPIcs, Volume 232, 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)


Abstract
The Quantum Approximate Optimization Algorithm (QAOA) finds approximate solutions to combinatorial optimization problems. Its performance monotonically improves with its depth p. We apply the QAOA to MaxCut on large-girth D-regular graphs. We give an iterative formula to evaluate performance for any D at any depth p. Looking at random D-regular graphs, at optimal parameters and as D goes to infinity, we find that the p = 11 QAOA beats all classical algorithms (known to the authors) that are free of unproven conjectures. While the iterative formula for these D-regular graphs is derived by looking at a single tree subgraph, we prove that it also gives the ensemble-averaged performance of the QAOA on the Sherrington-Kirkpatrick (SK) model defined on the complete graph. We also generalize our formula to Max-q-XORSAT on large-girth regular hypergraphs. Our iteration is a compact procedure, but its computational complexity grows as O(p² 4^p). This iteration is more efficient than the previous procedure for analyzing QAOA performance on the SK model, and we are able to numerically go to p = 20. Encouraged by our findings, we make the optimistic conjecture that the QAOA, as p goes to infinity, will achieve the Parisi value. We analyze the performance of the quantum algorithm, but one needs to run it on a quantum computer to produce a string with the guaranteed performance.

Cite as

Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, and Leo Zhou. The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model. In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 232, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{basso_et_al:LIPIcs.TQC.2022.7,
  author =	{Basso, Joao and Farhi, Edward and Marwaha, Kunal and Villalonga, Benjamin and Zhou, Leo},
  title =	{{The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model}},
  booktitle =	{17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)},
  pages =	{7:1--7:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-237-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{232},
  editor =	{Le Gall, Fran\c{c}ois and Morimae, Tomoyuki},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2022.7},
  URN =		{urn:nbn:de:0030-drops-165144},
  doi =		{10.4230/LIPIcs.TQC.2022.7},
  annote =	{Keywords: Quantum algorithm, Max-Cut, spin glass, approximation algorithm}
}
Document
Track A: Algorithms, Complexity and Games
Limitations of Local Quantum Algorithms on Random MAX-k-XOR and Beyond

Authors: Chi-Ning Chou, Peter J. Love, Juspreet Singh Sandhu, and Jonathan Shi

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)


Abstract
We introduce a notion of generic local algorithm, which strictly generalizes existing frameworks of local algorithms such as factors of i.i.d. by capturing local quantum algorithms such as the Quantum Approximate Optimization Algorithm (QAOA). Motivated by a question of Farhi et al. [arXiv:1910.08187, 2019], we then show limitations of generic local algorithms including QAOA on random instances of constraint satisfaction problems (CSPs). Specifically, we show that any generic local algorithm whose assignment to a vertex depends only on a local neighborhood with o(n) other vertices (such as the QAOA at depth less than εlog(n)) cannot arbitrarily-well approximate boolean CSPs if the problem satisfies a geometric property from statistical physics called the coupled overlap-gap property (OGP) [Chen et al., Annals of Probability, 47(3), 2019]. We show that the random MAX-k-XOR problem has this property when k ≥ 4 is even by extending the corresponding result for diluted k-spin glasses. Our concentration lemmas confirm a conjecture of Brandao et al. [arXiv:1812.04170, 2018] asserting that the landscape independence of QAOA extends to logarithmic depth - in other words, for every fixed choice of QAOA angle parameters, the algorithm at logarithmic depth performs almost equally well on almost all instances. One of these lemmas is a strengthening of McDiarmid’s inequality, applicable when the random variables have a highly biased distribution, and may be of independent interest.

Cite as

Chi-Ning Chou, Peter J. Love, Juspreet Singh Sandhu, and Jonathan Shi. Limitations of Local Quantum Algorithms on Random MAX-k-XOR and Beyond. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 41:1-41:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{chou_et_al:LIPIcs.ICALP.2022.41,
  author =	{Chou, Chi-Ning and Love, Peter J. and Sandhu, Juspreet Singh and Shi, Jonathan},
  title =	{{Limitations of Local Quantum Algorithms on Random MAX-k-XOR and Beyond}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{41:1--41:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.41},
  URN =		{urn:nbn:de:0030-drops-163822},
  doi =		{10.4230/LIPIcs.ICALP.2022.41},
  annote =	{Keywords: Quantum Algorithms, Spin Glasses, Hardness of Approximation, Local Algorithms, Concentration Inequalities, Overlap Gap Property}
}
Document
Eventually Sound Points-To Analysis with Specifications

Authors: Osbert Bastani, Rahul Sharma, Lazaro Clapp, Saswat Anand, and Alex Aiken

Published in: LIPIcs, Volume 134, 33rd European Conference on Object-Oriented Programming (ECOOP 2019)


Abstract
Static analyses make the increasingly tenuous assumption that all source code is available for analysis; for example, large libraries often call into native code that cannot be analyzed. We propose a points-to analysis that initially makes optimistic assumptions about missing code, and then inserts runtime checks that report counterexamples to these assumptions that occur during execution. Our approach guarantees eventual soundness, which combines two guarantees: (i) the runtime checks are guaranteed to catch the first counterexample that occurs during any execution, in which case execution can be terminated to prevent harm, and (ii) only finitely many counterexamples ever occur, implying that the static analysis eventually becomes statically sound with respect to all remaining executions. We implement Optix, an eventually sound points-to analysis for Android apps, where the Android framework is missing. We show that the runtime checks added by Optix incur low overhead on real programs, and demonstrate how Optix improves a client information flow analysis for detecting Android malware.

Cite as

Osbert Bastani, Rahul Sharma, Lazaro Clapp, Saswat Anand, and Alex Aiken. Eventually Sound Points-To Analysis with Specifications. In 33rd European Conference on Object-Oriented Programming (ECOOP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 134, pp. 11:1-11:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{bastani_et_al:LIPIcs.ECOOP.2019.11,
  author =	{Bastani, Osbert and Sharma, Rahul and Clapp, Lazaro and Anand, Saswat and Aiken, Alex},
  title =	{{Eventually Sound Points-To Analysis with Specifications}},
  booktitle =	{33rd European Conference on Object-Oriented Programming (ECOOP 2019)},
  pages =	{11:1--11:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-111-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{134},
  editor =	{Donaldson, Alastair F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2019.11},
  URN =		{urn:nbn:de:0030-drops-108038},
  doi =		{10.4230/LIPIcs.ECOOP.2019.11},
  annote =	{Keywords: specification inference, static points-to analysis, runtime monitoring}
}
Document
Bayesian ACRONYM Tuning

Authors: John Gamble, Christopher Granade, and Nathan Wiebe

Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)


Abstract
We provide an algorithm that uses Bayesian randomized benchmarking in concert with a local optimizer, such as SPSA, to find a set of controls that optimizes that average gate fidelity. We call this method Bayesian ACRONYM tuning as a reference to the analogous ACRONYM tuning algorithm. Bayesian ACRONYM distinguishes itself in its ability to retain prior information from experiments that use nearby control parameters; whereas traditional ACRONYM tuning does not use such information and can require many more measurements as a result. We prove that such information reuse is possible under the relatively weak assumption that the true model parameters are Lipschitz-continuous functions of the control parameters. We also perform numerical experiments that demonstrate that over-rotation errors in single qubit gates can be automatically tuned from 88% to 99.95% average gate fidelity using less than 1kB of data and fewer than 20 steps of the optimizer.

Cite as

John Gamble, Christopher Granade, and Nathan Wiebe. Bayesian ACRONYM Tuning. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 7:1-7:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{gamble_et_al:LIPIcs.TQC.2019.7,
  author =	{Gamble, John and Granade, Christopher and Wiebe, Nathan},
  title =	{{Bayesian ACRONYM Tuning}},
  booktitle =	{14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)},
  pages =	{7:1--7:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-112-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{135},
  editor =	{van Dam, Wim and Man\v{c}inska, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.7},
  URN =		{urn:nbn:de:0030-drops-103995},
  doi =		{10.4230/LIPIcs.TQC.2019.7},
  annote =	{Keywords: Quantum Computing, Randomized Benchmarking}
}
Document
Summary-Based Inter-Procedural Analysis via Modular Trace Refinement

Authors: Franck Cassez, Christian Müller, and Karla Burnett

Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)


Abstract
We propose a generalisation of trace refinement for the verification of inter-procedural programs. Our method is a top-down modular, summary-based approach, and analyses inter-procedural programs by building function summaries on-demand and improving the summaries each time a function is analysed. Our method is sound, and complete relative to the existence of a modular Hoare proof for a non-recursive program. We have implemented a prototype analyser that demonstrates the main features of our approach and yields promising results.

Cite as

Franck Cassez, Christian Müller, and Karla Burnett. Summary-Based Inter-Procedural Analysis via Modular Trace Refinement. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 545-556, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{cassez_et_al:LIPIcs.FSTTCS.2014.545,
  author =	{Cassez, Franck and M\"{u}ller, Christian and Burnett, Karla},
  title =	{{Summary-Based Inter-Procedural Analysis via Modular Trace Refinement}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{545--556},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Raman, Venkatesh and Suresh, S. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.545},
  URN =		{urn:nbn:de:0030-drops-48708},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.545},
  annote =	{Keywords: Program verification, Hoare Logic, Refinement, Automata}
}
  • Refine by Author
  • 2 Marwaha, Kunal
  • 2 Sandhu, Juspreet Singh
  • 2 Shi, Jonathan
  • 1 Aiken, Alex
  • 1 Anand, Saswat
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Randomness, geometry and discrete structures
  • 1 Hardware → Quantum computation
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Mathematics of computing → Combinatorics
  • 1 Mathematics of computing → Probabilistic algorithms
  • Show More...

  • Refine by Keyword
  • 2 spin glass
  • 1 Automata
  • 1 Concentration Inequalities
  • 1 Guerra-Toninelli interpolation
  • 1 Hardness of Approximation
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 2 2019
  • 2 2022
  • 1 2014
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail