We study the problem of chasing positive bodies in $\ell_1$: given a sequence of bodies $K_{t}=\{x^{t}\in\mathbb{R}_{+}^{n}\mid C^{t}x^{t}\geq 1,P^{t}x^{t}\leq 1\}$ revealed online, where $C^{t}$ and $P^{t}$ are nonnegative matrices, the goal is to (approximately) maintain a point $x_t \in K_t$ such that $\sum_t \|x_t - x_{t-1}\|_1$ is minimized. This captures the fully-dynamic low-recourse variant of any problem that can be expressed as a mixed packing-covering linear program and thus also the fractional version of many central problems in dynamic algorithms such as set cover, load balancing, hyperedge orientation, minimum spanning tree, and matching. We give an $O(\log d)$-competitive algorithm for this problem, where $d$ is the maximum row sparsity of any matrix $C^t$. This bypasses and improves exponentially over the lower bound of $\sqrt{n}$ known for general convex bodies. Our algorithm is based on iterated information projections, and, in contrast to general convex body chasing algorithms, is entirely memoryless. We also show how to round our solution dynamically to obtain the first fully dynamic algorithms with competitive recourse for all the stated problems above; i.e. their recourse is less than the recourse of every other algorithm on every update sequence, up to polylogarithmic factors. This is a significantly stronger notion than the notion of absolute recourse in the dynamic algorithms literature.
相關內容
Empowerment -- a domain independent, information-theoretic metric -- has previously been shown to assist in the evolutionary search for neural cellular automata (NCA) capable of homeostasis when employed as a fitness function. In our previous study, we successfully extended empowerment, defined as maximum time-lagged mutual information between agents' actions and future sensations, to a distributed sensorimotor system embodied as an NCA. However, the time-delay between actions and their corresponding sensations was arbitrarily chosen. Here, we expand upon previous work by exploring how the time scale at which empowerment operates impacts its efficacy as an auxiliary objective to accelerate the discovery of homeostatic NCAs. We show that shorter time delays result in marked improvements over empowerment with longer delays, when compared to evolutionary selection only for homeostasis. Moreover, we evaluate stability and adaptability of evolved NCAs, both hallmarks of living systems that are of interest to replicate in artificial ones. We find that short-term empowered NCA are more stable and are capable of generalizing better to unseen homeostatic challenges. Taken together, these findings motivate the use of empowerment during the evolution of other artifacts, and suggest how it should be incorporated to accelerate evolution of desired behaviors for them. Source code for the experiments in this paper can be found at: //github.com/caitlingrasso/empowered-nca-II.
A randomized algorithm for a search problem is *pseudodeterministic* if it produces a fixed canonical solution to the search problem with high probability. In their seminal work on the topic, Gat and Goldwasser posed as their main open problem whether prime numbers can be pseudodeterministically constructed in polynomial time. We provide a positive solution to this question in the infinitely-often regime. In more detail, we give an *unconditional* polynomial-time randomized algorithm $B$ such that, for infinitely many values of $n$, $B(1^n)$ outputs a canonical $n$-bit prime $p_n$ with high probability. More generally, we prove that for every dense property $Q$ of strings that can be decided in polynomial time, there is an infinitely-often pseudodeterministic polynomial-time construction of strings satisfying $Q$. This improves upon a subexponential-time construction of Oliveira and Santhanam. Our construction uses several new ideas, including a novel bootstrapping technique for pseudodeterministic constructions, and a quantitative optimization of the uniform hardness-randomness framework of Chen and Tell, using a variant of the Shaltiel--Umans generator.
In this work, we present how code generation techniques significantly improve the performance of the computational kernels in the HyTeG software framework. This HPC framework combines the performance and memory advantages of matrix-free multigrid solvers with the flexibility of unstructured meshes. The pystencils code generation toolbox is used to replace the original abstract C++ kernels with highly optimized loop nests. The performance of one of those kernels (the matrix-vector multiplication) is thoroughly analyzed using the Execution-Cache-Memory (ECM) performance model. We validate these predictions by measurements on the SuperMUC-NG supercomputer. The experiments show that the performance mostly matches the predictions. In cases where the prediction does not match, we discuss the discrepancies. Additionally, we conduct a node-level scaling study which shows the expected behavior for a memory-bound compute kernel.
The following hypothesis was put forward by Goreinov, Tyrtyshnikov and Zamarashkin in \cite{GTZ1997}. For arbitrary real $n \times k$ matrix with orthonormal columns a sufficiently "good" $k \times k$ submatrix exists. "Good" in the sense of having a bounded spectral norm of its inverse. The hypothesis says that for arbitrary $k = 1, \ldots, n-1$ the sharp upper bound is $\sqrt{n}$. Supported by numerical experiments, the problem remains open for all non-trivial cases ($1 < k < n-1$). In this paper, we will give the proof for the simplest of them ($n = 4, \, k = 2$).
We explore the performance of polynomial-time incentive-compatible mechanisms in single-crossing domains. Single-crossing domains were extensively studied in the economics literature. Roughly speaking, a domain is single crossing if monotonicity characterizes incentive compatibility. That is, single-crossing domains are the standard mathematical formulation of domains that are informally known as ``single parameter''. In all major single-crossing domains studied so far (e.g., welfare maximization in various auctions with single-minded bidders, makespan minimization on related machines), the performance of the best polynomial-time incentive-compatible mechanisms matches the performance of the best polynomial-time non-incentive-compatible algorithms. Our two main results make progress in understanding the power of incentive-compatible polynomial-time mechanisms in single-crossing domains: We provide the first proof of a gap in the power of polynomial-time incentive-compatible mechanisms and polynomial-time non-incentive-compatible algorithms: we present an objective function in a single-crossing multi-unit auction for which there is a polynomial-time algorithm that provides an approximation ratio of $\frac{1}{2}$, yet no polynomial-time incentive-compatible mechanism provides a finite approximation (under standard computational complexity assumptions). The objective function used above is not natural. We show that to some extent this is unavoidable by providing a sweeping positive result for the most natural objective function in multi-unit auctions, that of welfare maximization. We present an incentive-compatible FPTAS mechanism for every multi-unit auction with single-crossing domains. This improves over the mechanism of Briest et al. [STOC'05] that only applies to the much simpler case of single-minded bidders.
A substitution box (S-box) in a symmetric primitive is a mapping $F$ that takes $k$ binary inputs and whose image is a binary $m$-tuple for some positive integers $k$ and $m$, which is usually the only nonlinear element of the most modern block ciphers. Therefore, employing S-boxes with good cryptographic properties to resist various attacks is significant. For power permutation $F$ over finite field $\GF{2^k}$, the multiset of values $\beta_F(1,b)=\#\{x\in \GF{2^k}\mid F^{-1}(F(x)+b)+F^{-1}(F(x+1)+b)=1\}$ for $b\in \GF{2^k}$ is called the boomerang spectrum of $F$. The maximum value in the boomerang spectrum is called boomerang uniformity. This paper determines the boomerang spectrum of the power permutation $X^{2^{3n}+2^{2n}+2^{n}-1}$ over $\GF{2^{4n}}$. The boomerang uniformity of that power permutation is $3(2^{2n}-2^n)$. However, on a large subset $\{b\in \GF{2^{4n}}\mid \mathbf{Tr}_n^{4n}(b)\neq 0\}$ of $\GF{2^{4n}}$ of cardinality $2^{4n}-2^{3n}$ (where $ \mathbf{Tr}_n^{4n}$ is the (relative) trace function from $\GF{2^{4n}}$ to $\GF{2^{n}}$), we prove that the studied function $F$ achieves the optimal boomerang uniformity $2$. It is known that obtaining such functions is a challenging problem. More importantly, the set of $b$'s giving this value is explicitly determined for any value in the boomerang spectrum.
Adversarial team games model multiplayer strategic interactions in which a team of identically-interested players is competing against an adversarial player in a zero-sum game. Such games capture many well-studied settings in game theory, such as congestion games, but go well-beyond to environments wherein the cooperation of one team -- in the absence of explicit communication -- is obstructed by competing entities; the latter setting remains poorly understood despite its numerous applications. Since the seminal work of Von Stengel and Koller (GEB `97), different solution concepts have received attention from an algorithmic standpoint. Yet, the complexity of the standard Nash equilibrium has remained open. In this paper, we settle this question by showing that computing a Nash equilibrium in adversarial team games belongs to the class continuous local search (CLS), thereby establishing CLS-completeness by virtue of the recent CLS-hardness result of Rubinstein and Babichenko (STOC `21) in potential games. To do so, we leverage linear programming duality to prove that any $\epsilon$-approximate stationary strategy for the team can be extended in polynomial time to an $O(\epsilon)$-approximate Nash equilibrium, where the $O(\cdot)$ notation suppresses polynomial factors in the description of the game. As a consequence, we show that the Moreau envelop of a suitable best response function acts as a potential under certain natural gradient-based dynamics.
Suppose that we have $n$ agents and $n$ items which lie in a shared metric space. We would like to match the agents to items such that the total distance from agents to their matched items is as small as possible. However, instead of having direct access to distances in the metric, we only have each agent's ranking of the items in order of distance. Given this limited information, what is the minimum possible worst-case approximation ratio (known as the distortion) that a matching mechanism can guarantee? Previous work by Caragiannis et al. proved that the (deterministic) Serial Dictatorship mechanism has distortion at most $2^n - 1$. We improve this by providing a simple deterministic mechanism that has distortion $O(n^2)$. We also provide the first nontrivial lower bound on this problem, showing that any matching mechanism (deterministic or randomized) must have worst-case distortion $\Omega(\log n)$. In addition to these new bounds, we show that a large class of truthful mechanisms derived from Deferred Acceptance all have worst-case distortion at least $2^n - 1$, and we find an intriguing connection between thin matchings (analogous to the well-known thin trees conjecture) and the distortion gap between deterministic and randomized mechanisms.
We introduce a new parameter, called stretch-width, that we show sits strictly between clique-width and twin-width. Unlike the reduced parameters [BKW '22], planar graphs and polynomial subdivisions do not have bounded stretch-width. This leaves open the possibility of efficient algorithms for a broad fragment of problems within Monadic Second-Order (MSO) logic on graphs of bounded stretch-width. In this direction, we prove that graphs of bounded maximum degree and bounded stretch-width have at most logarithmic treewidth. As a consequence, in classes of bounded stretch-width, Maximum Independent Set can be solved in subexponential time $2^{O(n^{4/5} \log n)}$ on $n$-vertex graphs, and, if further the maximum degree is bounded, Existential Counting Modal Logic [Pilipczuk '11] can be model-checked in polynomial time. We also give a polynomial-time $O(\text{OPT}^2)$-approximation for the stretch-width of symmetric $0,1$-matrices or ordered graphs. Somewhat unexpectedly, we prove that exponential subdivisions of bounded-degree graphs have bounded stretch-width. This allows to complement the logarithmic upper bound of treewidth with a matching lower bound. We leave as open the existence of an efficient approximation algorithm for the stretch-width of unordered graphs, if the exponential subdivisions of all graphs have bounded stretch-width, and if graphs of bounded stretch-width have logarithmic clique-width (or rank-width).
Training machine learning (ML) algorithms is a computationally intensive process, which is frequently memory-bound due to repeatedly accessing large training datasets. As a result, processor-centric systems (e.g., CPU, GPU) suffer from costly data movement between memory units and processing units, which consumes large amounts of energy and execution cycles. Memory-centric computing systems, i.e., with processing-in-memory (PIM) capabilities, can alleviate this data movement bottleneck. Our goal is to understand the potential of modern general-purpose PIM architectures to accelerate ML training. To do so, we (1) implement several representative classic ML algorithms (namely, linear regression, logistic regression, decision tree, K-Means clustering) on a real-world general-purpose PIM architecture, (2) rigorously evaluate and characterize them in terms of accuracy, performance and scaling, and (3) compare to their counterpart implementations on CPU and GPU. Our evaluation on a real memory-centric computing system with more than 2500 PIM cores shows that general-purpose PIM architectures can greatly accelerate memory-bound ML workloads, when the necessary operations and datatypes are natively supported by PIM hardware. For example, our PIM implementation of decision tree is $27\times$ faster than a state-of-the-art CPU version on an 8-core Intel Xeon, and $1.34\times$ faster than a state-of-the-art GPU version on an NVIDIA A100. Our K-Means clustering on PIM is $2.8\times$ and $3.2\times$ than state-of-the-art CPU and GPU versions, respectively. To our knowledge, our work is the first one to evaluate ML training on a real-world PIM architecture. We conclude with key observations, takeaways, and recommendations that can inspire users of ML workloads, programmers of PIM architectures, and hardware designers & architects of future memory-centric computing systems.
小貼士
登錄享
相關主題
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191