Zobrazeno 1 - 10
of 668
pro vyhledávání: '"F.2.0"'
Context-free language (CFL) reachability is a standard approach in static analyses, where the analysis question is phrased as a language reachability problem on a graph $G$ wrt a CFL L. While CFLs lack the expressiveness needed for high precision, co
Externí odkaz:
http://arxiv.org/abs/2411.06383
Autor:
Sobczyk, Aleksandros
Optimizing data movements during program executions is essential for achieving high performance in modern computing systems. This has been classically modeled with the Red-Blue Pebble Game and its variants. In the existing models, it is typically ass
Externí odkaz:
http://arxiv.org/abs/2410.22237
In this article we show that Maximum Partial List H-Coloring is polynomial-time solvable on P_5-free graphs for every fixed graph H. In particular, this implies that Maximum k-Colorable Subgraph is polynomial-time solvable on P_5-free graphs. This an
Externí odkaz:
http://arxiv.org/abs/2410.21569
Autor:
De Stefani, Lorenzo, Gupta, Vedant
Asymptotically tight lower bounds are derived for the Input/Output (I/O) complexity of a class of dynamic programming algorithms including matrix chain multiplication, optimal polygon triangulation, and the construction of optimal binary search trees
Externí odkaz:
http://arxiv.org/abs/2410.20337
Autor:
Middelburg, C. A.
Previous papers give accounts of quests for satisfactory formalizations of the classical informal notion of an algorithm and the contemporary informal notion of an interactive algoritm. In this paper, an attempt is made to generalize the results of t
Externí odkaz:
http://arxiv.org/abs/2410.17821
Deep learning methods - consisting of a class of deep neural networks (DNNs) trained by a stochastic gradient descent (SGD) optimization method - are nowadays key tools to solve data driven supervised learning problems. Despite the great success of S
Externí odkaz:
http://arxiv.org/abs/2410.10533
Analog dynamical accelerators (DXs) are a growing sub-field in computer architecture research, offering order-of-magnitude gains in power efficiency and latency over traditional digital methods in several machine learning, optimization, and sampling
Externí odkaz:
http://arxiv.org/abs/2410.06397
We give two new approximation algorithms to compute the fractional hypertree width of an input hypergraph. The first algorithm takes as input $n$-vertex $m$-edge hypergraph $H$ of fractional hypertree width at most $\omega$, runs in polynomial time a
Externí odkaz:
http://arxiv.org/abs/2409.20172
Autor:
Hole, Arne
If an algorithm is to be counted as a practically working solution to a decision problem, then the algorithm must must verifiable in some constructed and ``trusted'' theory such as PA or ZF. In this paper, a class of decision problems related to inco
Externí odkaz:
http://arxiv.org/abs/2406.16843
Autor:
Streit, Robert, Garg, Vijay K.
Matroids provide one of the most elegant structures for algorithm design. This is best identified by the Edmonds-Rado theorem relating the success of the simple greedy algorithm to the anatomy of the optimal basis of a matroid [Edm71; Rad57]. As a re
Externí odkaz:
http://arxiv.org/abs/2408.04118