Zobrazeno 1 - 10
of 45 664
pro vyhledávání: '"computer science - data structures and algorithms"'
Autor:
Kavitha, Telikepalli, Makino, Kazuhisa
We consider a matching problem in a bipartite graph $G$ where every vertex has a capacity and a strict preference order on its neighbors. Furthermore, there is a cost function on the edge set. We assume $G$ admits a perfect matching, i.e., one that f
Externí odkaz:
http://arxiv.org/abs/2411.00384
Ateniese, Goodrich, Lekakis, Papamanthou, Paraskevas, and Tamassia introduced the Accountable Storage protocol, which is a way for a client to outsource their data to a cloud storage provider while allowing the client to periodically perform accounta
Externí odkaz:
http://arxiv.org/abs/2411.00255
Autor:
Arengas, Gustavo
Software bugs have caused enormous economic and human loss in recent years. Certified programming seeks to solve this problem by developing languages where we can make demonstrations that guarantee that our programs work properly. However, the rapid
Externí odkaz:
http://arxiv.org/abs/2411.00242
Autor:
Chang, Hsien-Chih, Cohen-Addad, Vincent, Conroy, Jonathan, Le, Hung, Pilipczuk, Marcin, Pilipczuk, Michał
Cohen-Addad, Le, Pilipczuk, and Pilipczuk [CLPP23] recently constructed a stochastic embedding with expected $1+\varepsilon$ distortion of $n$-vertex planar graphs (with polynomial aspect ratio) into graphs of treewidth $O(\varepsilon^{-1}\log^{13} n
Externí odkaz:
http://arxiv.org/abs/2411.00216
We consider the problems of testing and learning an unknown $n$-qubit Hamiltonian $H$ from queries to its evolution operator $e^{-iHt}$ under the normalized Frobenius norm. We prove: 1. Local Hamiltonians: We give a tolerant testing protocol to decid
Externí odkaz:
http://arxiv.org/abs/2411.00082
In recent years, there have been significant advances in efficiently solving $\ell_s$-regression using linear system solvers and $\ell_2$-regression [Adil-Kyng-Peng-Sachdeva, J. ACM'24]. Would efficient $\ell_p$-norm solvers lead to even faster rates
Externí odkaz:
http://arxiv.org/abs/2410.24158
We initiate the study of the following general clustering problem. We seek to partition a given set $P$ of data points into $k$ clusters by finding a set $X$ of $k$ centers and assigning each data point to one of the centers. The cost of a cluster, r
Externí odkaz:
http://arxiv.org/abs/2410.24104
Autor:
Caro, Matthias C., Eisert, Jens, Hinsche, Marcel, Ioannou, Marios, Nietner, Alexander, Sweke, Ryan
We consider the problem of testing and learning from data in the presence of resource constraints, such as limited memory or weak data access, which place limitations on the efficiency and feasibility of testing or learning. In particular, we ask the
Externí odkaz:
http://arxiv.org/abs/2410.23969
Autor:
Liu, Chih-Hung, Novikov, Gleb
We develop a technique to design efficiently computable estimators for sparse linear regression in the simultaneous presence of two adversaries: oblivious and adaptive. We design several robust algorithms that outperform the state of the art even in
Externí odkaz:
http://arxiv.org/abs/2410.23937
In this paper, we investigate the existence of parameterized algorithms running in subexponential time for two fundamental cycle-hitting problems: Feedback Vertex Set (FVS) and Triangle Hitting (TH). We focus on the class of pseudo-disk graphs, which
Externí odkaz:
http://arxiv.org/abs/2410.23878