Zobrazeno 1 - 10
of 63
pro vyhledávání: '"Kolla, Alexandra"'
We initiate the algorithmic study of the Quantum Max-$d$-Cut problem, a quantum generalization of the well-known Max-$d$-Cut problem. The Quantum Max-$d$-Cut problem involves finding a quantum state that maximizes the expected energy associated with
Externí odkaz:
http://arxiv.org/abs/2309.10957
We give a randomized algorithm that approximates the number of independent sets in a dense, regular bipartite graph -- in the language of approximate counting, we give an FPRAS for #BIS on the class of dense, regular bipartite graphs. Efficient count
Externí odkaz:
http://arxiv.org/abs/2307.09533
We compare the performance of a quantum local algorithm to a similar classical counterpart on a well-established combinatorial optimization problem LocalMaxCut. We show that a popular quantum algorithm first discovered by Farhi, Goldstone, and Gutman
Externí odkaz:
http://arxiv.org/abs/2304.08420
Autor:
Carlson, Charlie, Davies, Ewan, Fraiman, Nicolas, Kolla, Alexandra, Potukuchi, Aditya, Yap, Corrine
We give algorithms for approximating the partition function of the ferromagnetic $q$-color Potts model on graphs of maximum degree $d$. Our primary contribution is a fully polynomial-time approximation scheme for $d$-regular graphs with an expansion
Externí odkaz:
http://arxiv.org/abs/2204.01923
The ferromagnetic Ising model is a model of a magnetic material and a central topic in statistical physics. It also plays a starring role in the algorithmic study of approximate counting: approximating the partition function of the ferromagnetic Isin
Externí odkaz:
http://arxiv.org/abs/2111.03033
An emerging trend in approximate counting is to show that certain `low-temperature' problems are easy on typical instances, despite worst-case hardness results. For the class of regular graphs one usually shows that expansion can be exploited algorit
Externí odkaz:
http://arxiv.org/abs/2003.01154
We show how two techniques from statistical physics can be adapted to solve a variant of the notorious Unique Games problem, potentially opening new avenues towards the Unique Games Conjecture. The variant, which we call Count Unique Games, is a prom
Externí odkaz:
http://arxiv.org/abs/1911.01504
For a graph $G$, let $f(G)$ denote the size of the maximum cut in $G$. The problem of estimating $f(G)$ as a function of the number of vertices and edges of $G$ has a long history and was extensively studied in the last fifty years. In this paper we
Externí odkaz:
http://arxiv.org/abs/1810.10044
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
We initiate the study of spectral generalizations of the graph isomorphism problem. (a)The Spectral Graph Dominance (SGD) problem: On input of two graphs $G$ and $H$ does there exist a permutation $\pi$ such that $G\preceq \pi(H)$? (b) The Spectrally
Externí odkaz:
http://arxiv.org/abs/1805.00181