اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدTwo Results on Slime Mold Computations
45
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We present two results on slime mold computations. In wet-lab experiments (Nature00) by Nakagaki et al. the slime mold Physarum polycephalum demonstrated its ability to solve shortest path problems. Biologists proposed a mathematical model, a system of differential equations, for the slimes adaption process (J. Theoretical Biology07). It was shown that the process convergences to the shortest path (J. Theoretical Biology12) for all graphs. We show that the dynamics actually converges for a much wider class of problems, namely undirected linear programs with a non-negative cost vector. Combinatorial optimization researchers took the dynamics describing slime behavior as an inspiration for an optimization method and showed that its discretization can $varepsilon$-approximately solve linear programs with positive cost vector (ITCS16). Their analysis requires a feasible starting point, a step size depending linearly on $varepsilon$, and a number of steps with quartic dependence on $mathrm{opt}/(varepsilonPhi)$, where $Phi$ is the difference between the smallest cost of a non-optimal basic feasible solution and the optimal cost ($mathrm{opt}$). We give a refined analysis showing that the dynamics initialized with any strongly dominating point converges to the set of optimal solutions. Moreover, we strengthen the convergence rate bounds and prove that the step size is independent of $varepsilon$, and the number of steps depends logarithmically on $1/varepsilon$ and quadratically on $mathrm{opt}/Phi$.
قيم البحث
اقرأ أيضاً
We consider the problem of making distributed computations robust to noise, in particular to worst-case (adversarial) corruptions of messages. We give a general distributed interactive coding scheme which simulates any asynchronous distributed protoc
ol while tolerating an optimal corruption of a $Theta(1/n)$ fraction of all messages while incurring a moderate blowup of $O(nlog^2 n)$ in the communication complexity. Our result is the first fully distributed interactive coding scheme in which the topology of the communication network is not known in advance. Prior work required either a coordinating node to be connected to all other nodes in the network or assumed a synchronous network in which all nodes already know the complete topology of the network.
Hagfish slime is a unique predator defense material containing a network of long fibrous threads each ~ 10 cm in length. Hagfish release the threads in a condensed coiled state known as thread cells, or skeins (~ 100 microns), which must unravel with
in a fraction of a second to thwart a predator attack. Here we consider the hypothesis that viscous hydrodynamics can be responsible for this rapid unraveling, as opposed to chemical reaction kinetics alone. Our main conclusion is that, under reasonable physiological conditions, unraveling due to viscous drag can occur within a few hundred milliseconds, and is accelerated if the skein is pinned at a surface such as the mouth of a predator. We model a single thread cell unspooling as the fiber peels away due to viscous drag. We capture essential features by considering one-dimensional scenarios where the fiber is aligned with streamlines in either uniform flow or uniaxial extensional flow. The peeling resistance is modeled with a power-law dependence on peeling velocity. A dimensionless ratio of viscous drag to peeling resistance appears in the dynamical equations and determines the unraveling timescale. Our modeling approach is general and can be refined with future experimental measurements of peel strength for skein unraveling. It provides key insights into the unraveling process, offers potential answers to lingering questions about slime formation from threads and mucous vesicles, and will aid the growing interest in engineering similar bioinspired material systems.
We present a number of new results about range searching for colored (or categorical) data: 1. For a set of $n$ colored points in three dimensions, we describe randomized data structures with $O(nmathop{rm polylog}n)$ space that can report the dist
inct colors in any query orthogonal range (axis-aligned box) in $O(kmathop{rm polyloglog} n)$ expected time, where $k$ is the number of distinct colors in the range, assuming that coordinates are in ${1,ldots,n}$. Previous data structures require $O(frac{log n}{loglog n} + k)$ query time. Our result also implies improvements in higher constant dimensions. 2. Our data structures can be adapted to halfspace ranges in three dimensions (or circular ranges in two dimensions), achieving $O(klog n)$ expected query time. Previous data structures require $O(klog^2n)$ query time. 3. For a set of $n$ colored points in two dimensions, we describe a data structure with $O(nmathop{rm polylog}n)$ space that can answer colored type-2 range counting queries: report the number of occurrences of every distinct color in a query orthogonal range. The query time is $O(frac{log n}{loglog n} + kloglog n)$, where $k$ is the number of distinct colors in the range. Naively performing $k$ uncolored range counting queries would require $O(kfrac{log n}{loglog n})$ time. Our data structures are designed using a variety of techniques, including colored variants of randomized incremental construction (which may be of independent interest), colored variants of shallow cuttings, and bit-packing tricks.
We study the optimization problem associated with fitting two-layer ReLU neural networks with respect to the squared loss, where labels are generated by a target network. We make use of the rich symmetry structure to develop a novel set of tools for
studying families of spurious minima. In contrast to existing approaches which operate in limiting regimes, our technique directly addresses the nonconvex loss landscape for a finite number of inputs $d$ and neurons $k$, and provides analytic, rather than heuristic, information. In particular, we derive analytic estimates for the loss at different minima, and prove that modulo $O(d^{-1/2})$-terms the Hessian spectrum concentrates near small positive constants, with the exception of $Theta(d)$ eigenvalues which grow linearly with~$d$. We further show that the Hessian spectrum at global and spurious minima coincide to $O(d^{-1/2})$-order, thus challenging our ability to argue about statistical generalization through local curvature. Lastly, our technique provides the exact emph{fractional} dimensionality at which families of critical points turn from saddles into spurious minima. This makes possible the study of the creation and the annihilation of spurious minima using powerful tools from equivariant bifurcation theory.
In the classical Node-Disjoint Paths (NDP) problem, the input consists of an undirected $n$-vertex graph $G$, and a collection $mathcal{M}={(s_1,t_1),ldots,(s_k,t_k)}$ of pairs of its vertices, called source-destination, or demand, pairs. The goal is
to route the largest possible number of the demand pairs via node-disjoint paths. The best current approximation for the problem is achieved by a simple greedy algorithm, whose approximation factor is $O(sqrt n)$, while the best current negative result is an $Omega(log^{1/2-delta}n)$-hardness of approximation for any constant $delta$, under standard complexity assumptions. Even seemingly simple special cases of the problem are still poorly understood: when the input graph is a grid, the best current algorithm achieves an $tilde O(n^{1/4})$-approximation, and when it is a general planar graph, the best current approximation ratio of an efficient algorithm is $tilde O(n^{9/19})$. The best currently known lower bound on the approximability of both the
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
