We study the possibility of designing $N^{o(1)}$-round protocols for problems of substantially super-linear polynomial-time complexity on the congested clique with about $N^{1/2}$ nodes, where $N$ is the input size. We show that the exponent of the polynomial (if any) bounding the average time complexity of local computations performed at a node in such protocols has to be larger than that of the polynomial bounding the time complexity of the given problem.
相關內容
The $\ell_p$ subspace approximation problem is an NP-hard low rank approximation problem that generalizes the median hyperplane problem ($p = 1$), principal component analysis ($p = 2$), and the center hyperplane problem ($p = \infty$). A popular approach to cope with the NP-hardness of this problem is to compute a strong coreset, which is a small weighted subset of the input points which simultaneously approximates the cost of every $k$-dimensional subspace, typically to $(1+\varepsilon)$ relative error for a small constant $\varepsilon$. We obtain the first algorithm for constructing a strong coreset for $\ell_p$ subspace approximation with a nearly optimal dependence on the rank parameter $k$, obtaining a nearly linear bound of $\tilde O(k)\mathrm{poly}(\varepsilon^{-1})$ for $p<2$ and $\tilde O(k^{p/2})\mathrm{poly}(\varepsilon^{-1})$ for $p>2$. Prior constructions either achieved a similar size bound but produced a coreset with a modification of the original points [SW18, FKW21], or produced a coreset of the original points but lost $\mathrm{poly}(k)$ factors in the coreset size [HV20, WY23]. Our techniques also lead to the first nearly optimal online strong coresets for $\ell_p$ subspace approximation with similar bounds as the offline setting, resolving a problem of [WY23]. All prior approaches lose $\mathrm{poly}(k)$ factors in this setting, even when allowed to modify the original points.
Estimating parameters of functional ARMA, GARCH and invertible processes requires estimating lagged covariance and cross-covariance operators of Cartesian product Hilbert space-valued processes. Asymptotic results have been derived in recent years, either less generally or under a strict condition. This article derives upper bounds of the estimation errors for such operators based on the mild condition Lp-m-approximability for each lag, Cartesian power(s) and sample size, where the two processes can take values in different spaces in the context of lagged cross-covariance operators. Implications of our results on eigenelements, parameters in functional AR(MA) models and other general situations are also discussed.
We conduct a systematic study of the approximation properties of Transformer for sequence modeling with long, sparse and complicated memory. We investigate the mechanisms through which different components of Transformer, such as the dot-product self-attention, positional encoding and feed-forward layer, affect its expressive power, and we study their combined effects through establishing explicit approximation rates. Our study reveals the roles of critical parameters in the Transformer, such as the number of layers and the number of attention heads. These theoretical insights are validated experimentally and offer natural suggestions for alternative architectures.
Legged robot locomotion is hindered by a mismatch between applications where legs can outperform wheels or treads, most of which feature deformable substrates, and existing tools for planning and control, most of which assume flat, rigid substrates. In this study we focus on the ramifications of plastic terrain deformation on the hop-to-hop energy dynamics of a spring-legged monopedal hopping robot animated by a switched-compliance energy injection controller. From this deliberately simple robot-terrain template, we derive a hop-to-hop energy return map, and we use physical experiments and simulations to validate the hop-to-hop energy map for a real robot hopping on a real deformable substrate. The dynamical properties (fixed points, eigenvalues, basins of attraction) of this map provide insights into efficient, responsive, and robust locomotion on deformable terrain. Specifically, we identify constant-fixed-point surfaces in a controller parameter space that suggest it is possible to tune control parameters for efficiency or responsiveness while targeting a desired gait energy level. We also identify conditions under which fixed points of the energy map are globally stable, and we further characterize the basins of attraction of fixed points when these conditions are not satisfied. We conclude by discussing the implications of this hop-to-hop energy map for planning, control, and estimation for efficient, agile, and robust legged locomotion on deformable terrain.
The theory of forbidden 0-1 matrices generalizes Turan-style (bipartite) subgraph avoidance, Davenport-Schinzel theory, and Zarankiewicz-type problems, and has been influential in many areas, such as discrete and computational geometry, the analysis of self-adjusting data structures, and the development of the graph parameter twin width. The foremost open problems in this area is to resolve the Pach-Tardos conjecture from 2005, which states that if a forbidden pattern $P\in\{0,1\}^{k\times l}$ is the bipartite incidence matrix of an acyclic graph (forest), then $\mathrm{Ex}(P,n) = O(n\log^{C_P} n)$, where $C_P$ is a constant depending only on $P$. This conjecture has been confirmed on many small patterns, specifically all $P$ with weight at most 5, and all but two with weight 6. The main result of this paper is a clean refutation of the Pach-Tardos conjecture. Specifically, we prove that $\mathrm{Ex}(S_0,n),\mathrm{Ex}(S_1,n) \geq n2^{\Omega(\sqrt{\log n})}$, where $S_0,S_1$ are the outstanding weight-6 patterns. We also prove sharp bounds on the entire class of alternating patterns $(P_t)$, specifically that for every $t\geq 2$, $\mathrm{Ex}(P_t,n)=\Theta(n(\log n/\log\log n)^t)$. This is the first proof of an asymptotically sharp bound that is $\omega(n\log n)$.
We study whether the probability distribution of a discrete quantum walk can get arbitrarily close to uniform, given that the walk starts with a uniform superposition of the outgoing arcs of some vertex. We establish a characterization of this phenomenon on regular non-bipartite graphs in terms of their adjacency eigenvalues and eigenprojections. Using theory from association schemes, we show this phenomenon happens on a strongly regular graph $X$ if and only if $X$ or $\overline{X}$ has parameters $(4m^2, 2m^2\pm m, m^2\pm m, m^2\pm m)$ where $m\ge 2$.
We present fully abstract encodings of the call-by-name and call-by-value $\lambda$-calculus into HOcore, a minimal higher-order process calculus with no name restriction. We consider several equivalences on the $\lambda$-calculus side -- normal-form bisimilarity, applicative bisimilarity, and contextual equivalence -- that we internalize into abstract machines in order to prove full abstraction of the encodings. We also demonstrate that this technique scales to the $\lambda\mu$-calculus, i.e., a standard extension of the $\lambda$-calculus with control operators.
Digital quantum simulation has broad applications in approximating unitary evolution of Hamiltonians. In practice, many simulation tasks for quantum systems focus on quantum states in the low-energy subspace instead of the entire Hilbert space. In this paper, we systematically investigate the complexity of digital quantum simulation based on product formulas in the low-energy subspace. We show that the simulation error depends on the effective low-energy norm of the Hamiltonian for a variety of digital quantum simulation algorithms and quantum systems, allowing improvements over the previous complexities for full unitary simulations even for imperfect state preparations {due to thermalization}. In particular, for simulating spin models in the low-energy subspace, we prove that randomized product formulas such as qDRIFT and random permutation require smaller Trotter numbers. Such improvement also persists in symmetry-protected digital quantum simulations. We prove a similar improvement in simulating the dynamics of power-law quantum interactions. We also provide a query lower bound for general digital quantum simulations in the low-energy subspace.
We provide numerical evidence for a potential finite-time self-similar singularity of the 3D axisymmetric Euler equations with no swirl and with $C^\alpha$ initial vorticity for a large range of $\alpha$. We employ a highly effective adaptive mesh method to resolve the potential singularity sufficiently close to the potential blow-up time. Resolution study shows that our numerical method is at least second-order accurate. Scaling analysis and the dynamic rescaling method are presented to quantitatively study the scaling properties of the potential singularity. We demonstrate that this potential blow-up is stable with respect to the perturbation of initial data. Our numerical study shows that the 3D axisymmetric Euler equations with our initial data develop finite-time blow-up when the H\"older exponent $\alpha$ is smaller than some critical value $\alpha^*$, which has the potential to be $1/3$. We also study the $n$-dimensional axisymmetric Euler equations with no swirl, and observe that the critical H\"older exponent $\alpha^*$ is close to $1-\frac{2}{n}$. Compared with Elgindi's blow-up result in a similar setting \cite{elgindi2021finite}, our potential blow-up scenario has a different H\"older continuity property in the initial data and the scaling properties of the two initial data are also quite different. We also propose a relatively simple one-dimensional model and numerically verify its approximation to the $n$-dimensional axisymmetric Euler equations. This one-dimensional model sheds useful light to our understanding of the blow-up mechanism for the $n$-dimensional Euler equations.
In this work, a functional variant of the polynomial analogue of the classical Gandy's fixed point theorem is obtained. Sufficient conditions have been found to ensure that the complexity of the recursive function does not go beyond the polynomial. In 2021, we proved a polynomial analogue of the classical Gandy's fixed point theorem. This became an important impetus for the construction of p-complete programming languages. And such a language was first built by us in 2022. The main result of that work was: a solution of the problem P=L. Next are the followers of the works on building a new high-level language and the idea of building a general programming methodology. But there was one gap in our research: classes of recursive functions whose complexity was polynomial were not described. In this work we found sufficient conditions for such functions. In many ways, the main ideas of this work are similar to the ideas that we used in the proof of the polynomial analogue of Gandy's fixed point theorem. But there are also striking differences. Functions, as such, differ quite strongly from predicates precisely in the multitude of their values. If a predicate is either true or false, then a function can generally take on a variety of values. Moreover, even if there are not many values, but there is recursion and simple multiplication, then powers and factorials may arise during the calculations, which, of course, can violate the polynomial computational complexity of this function. Therefore, finding these restrictions on recursive functions that would be soft enough for the class of functions to be large, and at the same time tough enough not to go beyond polynomiality, has been a problem for us for the last 3 years, after the proof of the polynomial analogue Gandy's fixed point theorem in the case of predicate extensions.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191