@article{7757,
abstract = {Recent advances in designing metamaterials have demonstrated that global mechanical properties of disordered spring networks can be tuned by selectively modifying only a small subset of bonds. Here, using a computationally efficient approach, we extend this idea to tune more general properties of networks. With nearly complete success, we are able to produce a strain between any two target nodes in a network in response to an applied source strain on any other pair of nodes by removing only ∼1% of the bonds. We are also able to control multiple pairs of target nodes, each with a different individual response, from a single source, and to tune multiple independent source/target responses simultaneously into a network. We have fabricated physical networks in macroscopic 2D and 3D systems that exhibit these responses. This work is inspired by the long-range coupled conformational changes that constitute allosteric function in proteins. The fact that allostery is a common means for regulation in biological molecules suggests that it is a relatively easy property to develop through evolution. In analogy, our results show that long-range coupled mechanical responses are similarly easy to achieve in disordered networks.},
author = {Rocks, Jason W. and Pashine, Nidhi and Bischofberger, Irmgard and Goodrich, Carl Peter and Liu, Andrea J. and Nagel, Sidney R.},
issn = {0027-8424},
journal = {Proceedings of the National Academy of Sciences},
number = {10},
pages = {2520--2525},
publisher = {Proceedings of the National Academy of Sciences},
title = {{Designing allostery-inspired response in mechanical networks}},
doi = {10.1073/pnas.1612139114},
volume = {114},
year = {2017},
}
@article{7758,
abstract = {Controlling motion at the microscopic scale is a fundamental goal in the development of biologically inspired systems. We show that the motion of active, self-propelled colloids can be sufficiently controlled for use as a tool to assemble complex structures such as braids and weaves out of microscopic filaments. Unlike typical self-assembly paradigms, these structures are held together by geometric constraints rather than adhesive bonds. The out-of-equilibrium assembly that we propose involves precisely controlling the 2D motion of active colloids so that their path has a nontrivial topology. We demonstrate with proof-of-principle Brownian dynamics simulations that, when the colloids are attached to long semiflexible filaments, this motion causes the filaments to braid. The ability of the active particles to provide sufficient force necessary to bend the filaments into a braid depends on a number of factors, including the self-propulsion mechanism, the properties of the filament, and the maximum curvature in the braid. Our work demonstrates that nonequilibrium assembly pathways can be designed using active particles.},
author = {Goodrich, Carl Peter and Brenner, Michael P.},
issn = {0027-8424},
journal = {Proceedings of the National Academy of Sciences},
number = {2},
pages = {257--262},
publisher = {Proceedings of the National Academy of Sciences},
title = {{Using active colloids as machines to weave and braid on the micrometer scale}},
doi = {10.1073/pnas.1608838114},
volume = {114},
year = {2017},
}
@inproceedings{787,
abstract = {Population protocols are a popular model of distributed computing, in which randomly-interacting agents with little computational power cooperate to jointly perform computational tasks. Inspired by developments in molecular computation, and in particular DNA computing, recent algorithmic work has focused on the complexity of solving simple yet fundamental tasks in the population model, such as leader election (which requires convergence to a single agent in a special "leader" state), and majority (in which agents must converge to a decision as to which of two possible initial states had higher initial count). Known results point towards an inherent trade-off between the time complexity of such algorithms, and the space complexity, i.e. size of the memory available to each agent. In this paper, we explore this trade-off and provide new upper and lower bounds for majority and leader election. First, we prove a unified lower bound, which relates the space available per node with the time complexity achievable by a protocol: for instance, our result implies that any protocol solving either of these tasks for n agents using O(log log n) states must take (n=polylogn) expected time. This is the first result to characterize time complexity for protocols which employ super-constant number of states per node, and proves that fast, poly-logarithmic running times require protocols to have relatively large space costs. On the positive side, we give algorithms showing that fast, poly-logarithmic convergence time can be achieved using O(log2 n) space per node, in the case of both tasks. Overall, our results highlight a time complexity separation between O(log log n) and (log2 n) state space size for both majority and leader election in population protocols, and introduce new techniques, which should be applicable more broadly.},
author = {Alistarh, Dan-Adrian and Aspnes, James and Eisenstat, David and Rivest, Ronald and Gelashvili, Rati},
pages = {2560 -- 2579},
publisher = {SIAM},
title = {{Time-space trade-offs in population protocols}},
doi = {doi.org/10.1137/1.9781611974782.169},
year = {2017},
}
@inproceedings{788,
abstract = {In contrast to electronic computation, chemical computation is noisy and susceptible to a variety of sources of error, which has prevented the construction of robust complex systems. To be effective, chemical algorithms must be designed with an appropriate error model in mind. Here we consider the model of chemical reaction networks that preserve molecular count (population protocols), and ask whether computation can be made robust to a natural model of unintended “leak” reactions. Our definition of leak is motivated by both the particular spurious behavior seen when implementing chemical reaction networks with DNA strand displacement cascades, as well as the unavoidable side reactions in any implementation due to the basic laws of chemistry. We develop a new “Robust Detection” algorithm for the problem of fast (logarithmic time) single molecule detection, and prove that it is robust to this general model of leaks. Besides potential applications in single molecule detection, the error-correction ideas developed here might enable a new class of robust-by-design chemical algorithms. Our analysis is based on a non-standard hybrid argument, combining ideas from discrete analysis of population protocols with classic Markov chain techniques.},
author = {Alistarh, Dan-Adrian and Dudek, Bartłomiej and Kosowski, Adrian and Soloveichik, David and Uznański, Przemysław},
pages = {155 -- 171},
publisher = {Springer},
title = {{Robust detection in leak-prone population protocols}},
doi = {10.1007/978-3-319-66799-7_11},
volume = {10467 LNCS},
year = {2017},
}
@inproceedings{789,
abstract = {The problem of efficient concurrent memory reclamation in unmanaged languages such as C or C++ is one of the major challenges facing the parallelization of billions of lines of legacy code. Garbage collectors for C/C++ can be inefficient; thus, programmers are often forced to use finely-crafted concurrent memory reclamation techniques. These techniques can provide good performance, but require considerable programming effort to deploy, and have strict requirements, allowing the programmer very little room for error. In this work, we present Forkscan, a new conservative concurrent memory reclamation scheme which is fully automatic and surprisingly scalable. Forkscan's semantics place it between automatic garbage collectors (it requires the programmer to explicitly retire nodes before they can be reclaimed), and concurrent memory reclamation techniques (as it does not assume that nodes are completely unlinked from the data structure for correctness). Forkscan's implementation exploits these new semantics for efficiency: we leverage parallelism and optimized implementations of signaling and copy-on-write in modern operating systems to efficiently obtain and process consistent snapshots of memory that can be scanned concurrently with the normal program operation. Empirical evaluation on a range of classical concurrent data structure microbenchmarks shows that Forkscan can preserve the scalability of the original code, while maintaining an order of magnitude lower latency than automatic garbage collection, and demonstrating competitive performance with finely crafted memory reclamation techniques.},
author = {Alistarh, Dan-Adrian and Leiserson, William and Matveev, Alexander and Shavit, Nir},
pages = {483 -- 498},
publisher = {ACM},
title = {{Forkscan: Conservative memory reclamation for modern operating systems}},
doi = {10.1145/3064176.3064214},
year = {2017},
}
@inproceedings{790,
abstract = {Stochastic gradient descent (SGD) is a commonly used algorithm for training linear machine learning models. Based on vector algebra, it benefits from the inherent parallelism available in an FPGA. In this paper, we first present a single-precision floating-point SGD implementation on an FPGA that provides similar performance as a 10-core CPU. We then adapt the design to make it capable of processing low-precision data. The low-precision data is obtained from a novel compression scheme - called stochastic quantization, specifically designed for machine learning applications. We test both full-precision and low-precision designs on various regression and classification data sets. We achieve up to an order of magnitude training speedup when using low-precision data compared to a full-precision SGD on the same FPGA and a state-of-the-art multi-core solution, while maintaining the quality of training. We open source the designs presented in this paper.},
author = {Kara, Kaan and Alistarh, Dan-Adrian and Alonso, Gustavo and Mutlu, Onur and Zhang, Ce},
pages = {160 -- 167},
publisher = {IEEE},
title = {{FPGA-accelerated dense linear machine learning: A precision-convergence trade-off}},
doi = {10.1109/FCCM.2017.39},
year = {2017},
}
@inproceedings{791,
abstract = {Consider the following random process: we are given n queues, into which elements of increasing labels are inserted uniformly at random. To remove an element, we pick two queues at random, and remove the element of lower label (higher priority) among the two. The cost of a removal is the rank of the label removed, among labels still present in any of the queues, that is, the distance from the optimal choice at each step. Variants of this strategy are prevalent in state-of-the-art concurrent priority queue implementations. Nonetheless, it is not known whether such implementations provide any rank guarantees, even in a sequential model. We answer this question, showing that this strategy provides surprisingly strong guarantees: Although the single-choice process, where we always insert and remove from a single randomly chosen queue, has degrading cost, going to infinity as we increase the number of steps, in the two choice process, the expected rank of a removed element is O(n) while the expected worst-case cost is O(n log n). These bounds are tight, and hold irrespective of the number of steps for which we run the process. The argument is based on a new technical connection between "heavily loaded" balls-into-bins processes and priority scheduling. Our analytic results inspire a new concurrent priority queue implementation, which improves upon the state of the art in terms of practical performance.},
author = {Alistarh, Dan-Adrian and Kopinsky, Justin and Li, Jerry and Nadiradze, Giorgi},
booktitle = {Proceedings of the ACM Symposium on Principles of Distributed Computing},
isbn = {978-145034992-5},
location = {Washington, WA, USA},
pages = {283 -- 292},
publisher = {ACM},
title = {{The power of choice in priority scheduling}},
doi = {10.1145/3087801.3087810},
volume = {Part F129314},
year = {2017},
}
@article{792,
abstract = {The chaotic dynamics of low-dimensional systems, such as Lorenz or Rössler flows, is guided by the infinity of periodic orbits embedded in their strange attractors. Whether this is also the case for the infinite-dimensional dynamics of Navier–Stokes equations has long been speculated, and is a topic of ongoing study. Periodic and relative periodic solutions have been shown to be involved in transitions to turbulence. Their relevance to turbulent dynamics – specifically, whether periodic orbits play the same role in high-dimensional nonlinear systems like the Navier–Stokes equations as they do in lower-dimensional systems – is the focus of the present investigation. We perform here a detailed study of pipe flow relative periodic orbits with energies and mean dissipations close to turbulent values. We outline several approaches to reduction of the translational symmetry of the system. We study pipe flow in a minimal computational cell at Re=2500, and report a library of invariant solutions found with the aid of the method of slices. Detailed study of the unstable manifolds of a sample of these solutions is consistent with the picture that relative periodic orbits are embedded in the chaotic saddle and that they guide the turbulent dynamics.},
author = {Budanur, Nazmi B and Short, Kimberly and Farazmand, Mohammad and Willis, Ashley and Cvitanović, Predrag},
issn = {00221120},
journal = {Journal of Fluid Mechanics},
pages = {274 -- 301},
publisher = {Cambridge University Press},
title = {{Relative periodic orbits form the backbone of turbulent pipe flow}},
doi = {10.1017/jfm.2017.699},
volume = {833},
year = {2017},
}
@article{793,
abstract = {Let P be a finite point set in the plane. A cordinary triangle in P is a subset of P consisting of three non-collinear points such that each of the three lines determined by the three points contains at most c points of P . Motivated by a question of Erdös, and answering a question of de Zeeuw, we prove that there exists a constant c > 0such that P contains a c-ordinary triangle, provided that P is not contained in the union of two lines. Furthermore, the number of c-ordinary triangles in P is Ω(| P |). },
author = {Fulek, Radoslav and Mojarrad, Hossein and Naszódi, Márton and Solymosi, József and Stich, Sebastian and Szedlák, May},
issn = {09257721},
journal = {Computational Geometry: Theory and Applications},
pages = {28 -- 31},
publisher = {Elsevier},
title = {{On the existence of ordinary triangles}},
doi = {10.1016/j.comgeo.2017.07.002},
volume = {66},
year = {2017},
}
@article{794,
abstract = {We show that c-planarity is solvable in quadratic time for flat clustered graphs with three clusters if the combinatorial embedding of the underlying graph is fixed. In simpler graph-theoretical terms our result can be viewed as follows. Given a graph G with the vertex set partitioned into three parts embedded on a 2-sphere, our algorithm decides if we can augment G by adding edges without creating an edge-crossing so that in the resulting spherical graph the vertices of each part induce a connected sub-graph. We proceed by a reduction to the problem of testing the existence of a perfect matching in planar bipartite graphs. We formulate our result in a slightly more general setting of cyclic clustered graphs, i.e., the simple graph obtained by contracting each cluster, where we disregard loops and multi-edges, is a cycle.},
author = {Fulek, Radoslav},
journal = {Computational Geometry: Theory and Applications},
pages = {1 -- 13},
publisher = {Elsevier},
title = {{C-planarity of embedded cyclic c-graphs}},
doi = {10.1016/j.comgeo.2017.06.016},
volume = {66},
year = {2017},
}
@article{795,
abstract = {We introduce a common generalization of the strong Hanani–Tutte theorem and the weak Hanani–Tutte theorem: if a graph G has a drawing D in the plane where every pair of independent edges crosses an even number of times, then G has a planar drawing preserving the rotation of each vertex whose incident edges cross each other evenly in D. The theorem is implicit in the proof of the strong Hanani–Tutte theorem by Pelsmajer, Schaefer and Štefankovič. We give a new, somewhat simpler proof.},
author = {Fulek, Radoslav and Kynčl, Jan and Pálvölgyi, Dömötör},
issn = {10778926},
journal = {Electronic Journal of Combinatorics},
number = {3},
publisher = {International Press},
title = {{Unified Hanani Tutte theorem}},
volume = {24},
year = {2017},
}
@article{463,
abstract = {We investigate transient behaviors induced by magnetic fields on the dynamics of the flow of a ferrofluid in the gap between two concentric, independently rotating cylinders. Without applying any magnetic fields, we uncover emergence of flow states constituted by a combination of a localized spiral state (SPIl) in the top and bottom of the annulus and different multi-cell flow states (SPI2v, SPI3v) with toroidally closed vortices in the interior of the bulk (SPIl+2v = SPIl + SPI2v and SPIl+3v = SPIl + SPI3v). However, when a magnetic field is presented, we observe the transient behaviors between multi-cell states passing through two critical thresholds in a strength of an axial (transverse) magnetic field. Before the first critical threshold of a magnetic field strength, multi-stable states with different number of cells could be observed. After the first critical threshold, we find the transient behavior between the three- and two-cell flow states. For more strength of magnetic field or after the second critical threshold, we discover that multi-cell states are disappeared and a localized spiral state remains to be stimulated. The studied transient behavior could be understood by the investigation of various quantities including a modal kinetic energy, a mode amplitude of the radial velocity, wavenumber, angular momentum, and torque. In addition, the emergence of new flow states and the transient behavior between their states in ferrofluidic flows indicate that richer and potentially controllable dynamics through magnetic fields could be possible in ferrofluic flow.},
author = {Altmeyer, Sebastian and Do, Younghae and Ryu, Soorok},
issn = {10541500},
journal = {Chaos},
number = {11},
publisher = {AIP},
title = {{Transient behavior between multi-cell flow states in ferrofluidic Taylor-Couette flow}},
doi = {10.1063/1.5002771},
volume = {27},
year = {2017},
}
@article{464,
abstract = {The computation of the winning set for parity objectives and for Streett objectives in graphs as well as in game graphs are central problems in computer-aided verification, with application to the verification of closed systems with strong fairness conditions, the verification of open systems, checking interface compatibility, well-formedness of specifications, and the synthesis of reactive systems. We show how to compute the winning set on n vertices for (1) parity-3 (aka one-pair Streett) objectives in game graphs in time O(n5/2) and for (2) k-pair Streett objectives in graphs in time O(n2+nklogn). For both problems this gives faster algorithms for dense graphs and represents the first improvement in asymptotic running time in 15 years.},
author = {Chatterjee, Krishnendu and Henzinger, Monika and Loitzenbauer, Veronika},
issn = {18605974},
journal = {Logical Methods in Computer Science},
number = {3},
publisher = {International Federation of Computational Logic},
title = {{Improved algorithms for parity and Streett objectives}},
doi = {10.23638/LMCS-13(3:26)2017},
volume = {13},
year = {2017},
}
@article{465,
abstract = {The edit distance between two words w 1 , w 2 is the minimal number of word operations (letter insertions, deletions, and substitutions) necessary to transform w 1 to w 2 . The edit distance generalizes to languages L 1 , L 2 , where the edit distance from L 1 to L 2 is the minimal number k such that for every word from L 1 there exists a word in L 2 with edit distance at most k . We study the edit distance computation problem between pushdown automata and their subclasses. The problem of computing edit distance to a pushdown automaton is undecidable, and in practice, the interesting question is to compute the edit distance from a pushdown automaton (the implementation, a standard model for programs with recursion) to a regular language (the specification). In this work, we present a complete picture of decidability and complexity for the following problems: (1) deciding whether, for a given threshold k , the edit distance from a pushdown automaton to a finite automaton is at most k , and (2) deciding whether the edit distance from a pushdown automaton to a finite automaton is finite. },
author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Ibsen-Jensen, Rasmus and Otop, Jan},
issn = {18605974},
journal = {Logical Methods in Computer Science},
number = {3},
publisher = {International Federation of Computational Logic},
title = {{Edit distance for pushdown automata}},
doi = {10.23638/LMCS-13(3:23)2017},
volume = {13},
year = {2017},
}
@article{466,
abstract = {We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives. There exist two different views: (i) the expectation semantics, where the goal is to optimize the expected mean-payoff objective, and (ii) the satisfaction semantics, where the goal is to maximize the probability of runs such that the mean-payoff value stays above a given vector. We consider optimization with respect to both objectives at once, thus unifying the existing semantics. Precisely, the goal is to optimize the expectation while ensuring the satisfaction constraint. Our problem captures the notion of optimization with respect to strategies that are risk-averse (i.e., ensure certain probabilistic guarantee). Our main results are as follows: First, we present algorithms for the decision problems which are always polynomial in the size of the MDP. We also show that an approximation of the Pareto-curve can be computed in time polynomial in the size of the MDP, and the approximation factor, but exponential in the number of dimensions. Second, we present a complete characterization of the strategy complexity (in terms of memory bounds and randomization) required to solve our problem. },
author = {Chatterjee, Krishnendu and Křetínská, Zuzana and Kretinsky, Jan},
issn = {18605974},
journal = {Logical Methods in Computer Science},
number = {2},
publisher = {International Federation of Computational Logic},
title = {{Unifying two views on multiple mean-payoff objectives in Markov decision processes}},
doi = {10.23638/LMCS-13(2:15)2017},
volume = {13},
year = {2017},
}
@article{467,
abstract = {Recently there has been a significant effort to handle quantitative properties in formal verification and synthesis. While weighted automata over finite and infinite words provide a natural and flexible framework to express quantitative properties, perhaps surprisingly, some basic system properties such as average response time cannot be expressed using weighted automata or in any other known decidable formalism. In this work, we introduce nested weighted automata as a natural extension of weighted automata, which makes it possible to express important quantitative properties such as average response time. In nested weighted automata, a master automaton spins off and collects results from weighted slave automata, each of which computes a quantity along a finite portion of an infinite word. Nested weighted automata can be viewed as the quantitative analogue of monitor automata, which are used in runtime verification. We establish an almost-complete decidability picture for the basic decision problems about nested weighted automata and illustrate their applicability in several domains. In particular, nested weighted automata can be used to decide average response time properties.},
author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Otop, Jan},
issn = {15293785},
journal = {ACM Transactions on Computational Logic (TOCL)},
number = {4},
publisher = {ACM},
title = {{Nested weighted automata}},
doi = {10.1145/3152769},
volume = {18},
year = {2017},
}
@article{470,
abstract = {This paper presents a method for simulating water surface waves as a displacement field on a 2D domain. Our method relies on Lagrangian particles that carry packets of water wave energy; each packet carries information about an entire group of wave trains, as opposed to only a single wave crest. Our approach is unconditionally stable and can simulate high resolution geometric details. This approach also presents a straightforward interface for artistic control, because it is essentially a particle system with intuitive parameters like wavelength and amplitude. Our implementation parallelizes well and runs in real time for moderately challenging scenarios.},
author = {Jeschke, Stefan and Wojtan, Christopher J},
issn = {07300301},
journal = {ACM Transactions on Graphics},
number = {4},
publisher = {ACM},
title = {{Water wave packets}},
doi = {10.1145/3072959.3073678},
volume = {36},
year = {2017},
}
@article{471,
abstract = {We present a new algorithm for the statistical model checking of Markov chains with respect to unbounded temporal properties, including full linear temporal logic. The main idea is that we monitor each simulation run on the fly, in order to detect quickly if a bottom strongly connected component is entered with high probability, in which case the simulation run can be terminated early. As a result, our simulation runs are often much shorter than required by termination bounds that are computed a priori for a desired level of confidence on a large state space. In comparison to previous algorithms for statistical model checking our method is not only faster in many cases but also requires less information about the system, namely, only the minimum transition probability that occurs in the Markov chain. In addition, our method can be generalised to unbounded quantitative properties such as mean-payoff bounds. },
author = {Daca, Przemyslaw and Henzinger, Thomas A and Kretinsky, Jan and Petrov, Tatjana},
issn = {15293785},
journal = {ACM Transactions on Computational Logic (TOCL)},
number = {2},
publisher = {ACM},
title = {{Faster statistical model checking for unbounded temporal properties}},
doi = {10.1145/3060139},
volume = {18},
year = {2017},
}
@article{472,
abstract = {α-Synuclein is a presynaptic protein the function of which has yet to be identified, but its neuronal content increases in patients of synucleinopa-thies including Parkinson’s disease. Chronic overexpression of α-synuclein reportedly expresses various phenotypes of synaptic dysfunction, but the primary target of its toxicity has not been determined. To investigate this, we acutely loaded human recombinant α-synuclein or its pathological mutants in their monomeric forms into the calyces of Held presynaptic terminals in slices from auditorily mature and immature rats of either sex. Membrane capacitance measurements revealed significant and specific inhibitory effects of WT monomeric α-synuclein on vesicle endocytosis throughout development. However, the α-synuclein A53T mutant affected vesicle endocytosis only at immature calyces, where as the A30P mutant had no effect throughout. The endocytic impairment by WTα-synuclein was rescued by intraterminal coloading of the microtubule (MT) polymerization blocker nocodazole. Furthermore, it was reversibly rescued by presynaptically loaded photostatin-1, a pho-toswitcheable inhibitor of MT polymerization, inalight-wavelength-dependent manner. Incontrast, endocyticinhibition by the A53T mutant at immature calyces was not rescued by nocodazole. Functionally, presynaptically loaded WT α-synuclein had no effect on basal synaptic transmission evoked at a low frequency, but significantly attenuated exocytosis and impaired the fidelity of neurotransmission during prolonged high-frequency stimulation. We conclude that monomeric WTα-synuclein primarily inhibits vesicle endocytosis via MT overassembly, thereby impairing high-frequency neurotransmission.},
author = {Eguchi, Kohgaku and Taoufiq, Zachari and Thorn Seshold, Oliver and Trauner, Dirk and Hasegawa, Masato and Takahashi, Tomoyuki},
issn = {02706474},
journal = {European Journal of Neuroscience},
number = {25},
pages = {6043 -- 6052},
publisher = {Wiley-Blackwell},
title = {{Wild-type monomeric α-synuclein can impair vesicle endocytosis and synaptic fidelity via tubulin polymerization at the calyx of held}},
doi = {10.1523/JNEUROSCI.0179-17.2017},
volume = {37},
year = {2017},
}
@article{481,
abstract = {We introduce planar matchings on directed pseudo-line arrangements, which yield a planar set of pseudo-line segments such that only matching-partners are adjacent. By translating the planar matching problem into a corresponding stable roommates problem we show that such matchings always exist. Using our new framework, we establish, for the first time, a complete, rigorous definition of weighted straight skeletons, which are based on a so-called wavefront propagation process. We present a generalized and unified approach to treat structural changes in the wavefront that focuses on the restoration of weak planarity by finding planar matchings.},
author = {Biedl, Therese and Huber, Stefan and Palfrader, Peter},
journal = {International Journal of Computational Geometry and Applications},
number = {3-4},
pages = {211 -- 229},
publisher = {World Scientific Publishing},
title = {{Planar matchings for weighted straight skeletons}},
doi = {10.1142/S0218195916600050},
volume = {26},
year = {2017},
}