16 Search Results for "Randall, Dana"

Document
DOI: 10.4230/LIPIcs.FSCD.2024.10
Second-Order Generalised Algebraic Theories: Signatures and First-Order Semantics

Authors: Ambrus Kaposi and Szumi Xie

Published in: LIPIcs, Volume 299, 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)

Abstract
Programming languages can be defined from the concrete to the abstract by abstract syntax trees, well-scoped syntax, well-typed (intrinsic) syntax, algebraic syntax (well-typed syntax quotiented by conversion). Another aspect is the representation of binding structure for which nominal approaches, De Bruijn indices/levels and higher order abstract syntax (HOAS) are available. In HOAS, binders are given by the function space of an internal language of presheaves. In this paper, we show how to combine the algebraic approach with the HOAS approach: following Uemura, we define languages as second-order generalised algebraic theories (SOGATs). Through a series of examples we show that non-substructural languages can be naturally defined as SOGATs. We give a formal definition of SOGAT signatures (using the syntax of a particular SOGAT) and define two translations from SOGAT signatures to GAT signatures (signatures for quotient inductive-inductive types), based on parallel and single substitutions, respectively.
Cite as

Ambrus Kaposi and Szumi Xie. Second-Order Generalised Algebraic Theories: Signatures and First-Order Semantics. In 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 299, pp. 10:1-10:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kaposi_et_al:LIPIcs.FSCD.2024.10,
  author =	{Kaposi, Ambrus and Xie, Szumi},
  title =	{{Second-Order Generalised Algebraic Theories: Signatures and First-Order Semantics}},
  booktitle =	{9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)},
  pages =	{10:1--10:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-323-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{299},
  editor =	{Rehof, Jakob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2024.10},
  URN =		{urn:nbn:de:0030-drops-203396},
  doi =		{10.4230/LIPIcs.FSCD.2024.10},
  annote =	{Keywords: Type theory, universal algebra, inductive types, quotient inductive types, higher-order abstract syntax, logical framework}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.16
NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials

Authors: Omkar Baraskar, Agrim Dewan, Chandan Saha, and Pulkit Sinha

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
An s-sparse polynomial has at most s monomials with nonzero coefficients. The Equivalence Testing problem for sparse polynomials (ETsparse) asks to decide if a given polynomial f is equivalent to (i.e., in the orbit of) some s-sparse polynomial. In other words, given f ∈ 𝔽[𝐱] and s ∈ ℕ, ETsparse asks to check if there exist A ∈ GL(|𝐱|, 𝔽) and 𝐛 ∈ 𝔽^|𝐱| such that f(A𝐱 + 𝐛) is s-sparse. We show that ETsparse is NP-hard over any field 𝔽, if f is given in the sparse representation, i.e., as a list of nonzero coefficients and exponent vectors. This answers a question posed by Gupta, Saha and Thankey (SODA 2023) and also, more explicitly, by Baraskar, Dewan and Saha (STACS 2024). The result implies that the Minimum Circuit Size Problem (MCSP) is NP-hard for a dense subclass of depth-3 arithmetic circuits if the input is given in sparse representation. We also show that approximating the smallest s₀ such that a given s-sparse polynomial f is in the orbit of some s₀-sparse polynomial to within a factor of s^{1/3 - ε} is NP-hard for any ε > 0; observe that s-factor approximation is trivial as the input is s-sparse. Finally, we show that for any constant σ ≥ 6, checking if a polynomial (given in sparse representation) is in the orbit of some support-σ polynomial is NP-hard. Support of a polynomial f is the maximum number of variables present in any monomial of f. These results are obtained via direct reductions from the 3-SAT problem.
Cite as

Omkar Baraskar, Agrim Dewan, Chandan Saha, and Pulkit Sinha. NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 16:1-16:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{baraskar_et_al:LIPIcs.ICALP.2024.16,
  author =	{Baraskar, Omkar and Dewan, Agrim and Saha, Chandan and Sinha, Pulkit},
  title =	{{NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{16:1--16:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.16},
  URN =		{urn:nbn:de:0030-drops-201598},
  doi =		{10.4230/LIPIcs.ICALP.2024.16},
  annote =	{Keywords: Equivalence testing, MCSP, sparse polynomials, 3SAT}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.29
A Tight Monte-Carlo Algorithm for Steiner Tree Parameterized by Clique-Width

Authors: Narek Bojikian and Stefan Kratsch

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
Given a graph G = (V,E), a set T ⊆ V, and an integer b, the Steiner Tree problem asks whether G has a connected subgraph H with at most b vertices that spans all of T. This work presents a 3^k⋅ n^𝒪(1) time one-sided Monte-Carlo algorithm for solving Steiner Tree when additionally a clique-expression of width k is provided. Known lower bounds for less expressive parameters imply that this dependence on the clique-width of G is optimal assuming the Strong Exponential-Time Hypothesis (SETH). Indeed our work establishes that the parameter dependence of Steiner Tree is the same for any graph parameter between cutwidth and clique-width, assuming SETH. Our work contributes to the program of determining the exact parameterized complexity of fundamental hard problems relative to structural graph parameters such as treewidth, which was initiated by Lokshtanov et al. [SODA 2011 & TALG 2018] and which by now has seen a plethora of results. Since the cut-and-count framework of Cygan et al. [FOCS 2011 & TALG 2022], connectivity problems have played a key role in this program as they pose many challenges for developing tight upper and lower bounds. Recently, Hegerfeld and Kratsch [ESA 2023] gave the first application of the cut-and-count technique to problems parameterized by clique-width and obtained tight bounds for Connected Dominating Set and Connected Vertex Cover, leaving open the complexity of other benchmark connectivity problems such as Steiner Tree and Feedback Vertex Set. Our algorithm for Steiner Tree does not follow the cut-and-count technique and instead works with the connectivity patterns of partial solutions. As a first technical contribution we identify a special family of so-called complete patterns that has strong (existential) representation properties, and using these at least one solution will be preserved. Furthermore, there is a family of 3^k basis patterns that (parity) represents the complete patterns, i.e., it has the same number of solutions modulo two. Our main technical contribution, a new technique called "isolating a representative," allows us to leverage both forms of representation (existential and parity). Both complete patterns and isolation of a representative will likely be applicable to other (connectivity) problems.
Cite as

Narek Bojikian and Stefan Kratsch. A Tight Monte-Carlo Algorithm for Steiner Tree Parameterized by Clique-Width. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 29:1-29:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bojikian_et_al:LIPIcs.ICALP.2024.29,
  author =	{Bojikian, Narek and Kratsch, Stefan},
  title =	{{A Tight Monte-Carlo Algorithm for Steiner Tree Parameterized by Clique-Width}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{29:1--29:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.29},
  URN =		{urn:nbn:de:0030-drops-201728},
  doi =		{10.4230/LIPIcs.ICALP.2024.29},
  annote =	{Keywords: Parameterized complexity, Steiner tree, clique-width}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.58
New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths

Authors: Michal Dory, Sebastian Forster, Yasamin Nazari, and Tijn de Vos

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We provide new tradeoffs between approximation and running time for the decremental all-pairs shortest paths (APSP) problem. For undirected graphs with m edges and n nodes undergoing edge deletions, we provide four new approximate decremental APSP algorithms, two for weighted and two for unweighted graphs. Our first result is (2+ε)-APSP with total update time Õ(m^{1/2}n^{3/2}) (when m = n^{1+c} for any constant 0 < c < 1). Prior to our work the fastest algorithm for weighted graphs with approximation at most 3 had total Õ(mn) update time for (1+ε)-APSP [Bernstein, SICOMP 2016]. Our second result is (2+ε, W_{u,v})-APSP with total update time Õ(nm^{3/4}), where the second term is an additive stretch with respect to W_{u,v}, the maximum weight on the shortest path from u to v. Our third result is (2+ε)-APSP for unweighted graphs in Õ(m^{7/4}) update time, which for sparse graphs (m = o(n^{8/7})) is the first subquadratic (2+ε)-approximation. Our last result for unweighted graphs is (1+ε, 2(k-1))-APSP, for k ≥ 2, with Õ(n^{2-1/k}m^{1/k}) total update time (when m = n^{1+c} for any constant c > 0). For comparison, in the special case of (1+ε, 2)-approximation, this improves over the state-of-the-art algorithm by [Henzinger, Krinninger, Nanongkai, SICOMP 2016] with total update time of Õ(n^{2.5}). All of our results are randomized, work against an oblivious adversary, and have constant query time.
Cite as

Michal Dory, Sebastian Forster, Yasamin Nazari, and Tijn de Vos. New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 58:1-58:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dory_et_al:LIPIcs.ICALP.2024.58,
  author =	{Dory, Michal and Forster, Sebastian and Nazari, Yasamin and de Vos, Tijn},
  title =	{{New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{58:1--58:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.58},
  URN =		{urn:nbn:de:0030-drops-202012},
  doi =		{10.4230/LIPIcs.ICALP.2024.58},
  annote =	{Keywords: Decremental Shortest Path, All-Pairs Shortest Paths}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.60
Testing C_k-Freeness in Bounded-Arboricity Graphs

Authors: Talya Eden, Reut Levi, and Dana Ron

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We study the problem of testing C_k-freeness (k-cycle-freeness) for fixed constant k > 3 in graphs with bounded arboricity (but unbounded degrees). In particular, we are interested in one-sided error algorithms, so that they must detect a copy of C_k with high constant probability when the graph is ε-far from C_k-free. We next state our results for constant arboricity and constant ε with a focus on the dependence on the number of graph vertices, n. The query complexity of all our algorithms grows polynomially with 1/ε. 1) As opposed to the case of k = 3, where the complexity of testing C₃-freeness grows with the arboricity of the graph but not with the size of the graph (Levi, ICALP 2021) this is no longer the case already for k = 4. We show that Ω(n^{1/4}) queries are necessary for testing C₄-freeness, and that Õ(n^{1/4}) are sufficient. The same bounds hold for C₅. 2) For every fixed k ≥ 6, any one-sided error algorithm for testing C_k-freeness must perform Ω(n^{1/3}) queries. 3) For k = 6 we give a testing algorithm whose query complexity is Õ(n^{1/2}). 4) For any fixed k, the query complexity of testing C_k-freeness is upper bounded by {O}(n^{1-1/⌊k/2⌋}). The last upper bound builds on another result in which we show that for any fixed subgraph F, the query complexity of testing F-freeness is upper bounded by O(n^{1-1/𝓁(F)}), where 𝓁(F) is a parameter of F that is always upper bounded by the number of vertices in F (and in particular is k/2 in C_k for even k). We extend some of our results to bounded (non-constant) arboricity, where in particular, we obtain sublinear upper bounds for all k. Our Ω(n^{1/4}) lower bound for testing C₄-freeness in constant arboricity graphs provides a negative answer to an open problem posed by (Goldreich, 2021).
Cite as

Talya Eden, Reut Levi, and Dana Ron. Testing C_k-Freeness in Bounded-Arboricity Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 60:1-60:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{eden_et_al:LIPIcs.ICALP.2024.60,
  author =	{Eden, Talya and Levi, Reut and Ron, Dana},
  title =	{{Testing C\underlinek-Freeness in Bounded-Arboricity Graphs}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{60:1--60:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.60},
  URN =		{urn:nbn:de:0030-drops-202033},
  doi =		{10.4230/LIPIcs.ICALP.2024.60},
  annote =	{Keywords: Property Testing, Cycle-Freeness, Bounded Arboricity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.86
Problems on Group-Labeled Matroid Bases

Authors: Florian Hörsch, András Imolay, Ryuhei Mizutani, Taihei Oki, and Tamás Schwarcz

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
Consider a matroid equipped with a labeling of its ground set to an abelian group. We define the label of a subset of the ground set as the sum of the labels of its elements. We study a collection of problems on finding bases and common bases of matroids with restrictions on their labels. For zero bases and zero common bases, the results are mostly negative. While finding a non-zero basis of a matroid is not difficult, it turns out that the complexity of finding a non-zero common basis depends on the group. Namely, we show that the problem is hard for a fixed group if it contains an element of order two, otherwise it is polynomially solvable. As a generalization of both zero and non-zero constraints, we further study F-avoiding constraints where we seek a basis or common basis whose label is not in a given set F of forbidden labels. Using algebraic techniques, we give a randomized algorithm for finding an F-avoiding common basis of two matroids represented over the same field for finite groups given as operation tables. The study of F-avoiding bases with groups given as oracles leads to a conjecture stating that whenever an F-avoiding basis exists, an F-avoiding basis can be obtained from an arbitrary basis by exchanging at most |F| elements. We prove the conjecture for the special cases when |F| ≤ 2 or the group is ordered. By relying on structural observations on matroids representable over fixed, finite fields, we verify a relaxed version of the conjecture for these matroids. As a consequence, we obtain a polynomial-time algorithm in these special cases for finding an F-avoiding basis when |F| is fixed.
Cite as

Florian Hörsch, András Imolay, Ryuhei Mizutani, Taihei Oki, and Tamás Schwarcz. Problems on Group-Labeled Matroid Bases. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 86:1-86:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{horsch_et_al:LIPIcs.ICALP.2024.86,
  author =	{H\"{o}rsch, Florian and Imolay, Andr\'{a}s and Mizutani, Ryuhei and Oki, Taihei and Schwarcz, Tam\'{a}s},
  title =	{{Problems on Group-Labeled Matroid Bases}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{86:1--86:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.86},
  URN =		{urn:nbn:de:0030-drops-202299},
  doi =		{10.4230/LIPIcs.ICALP.2024.86},
  annote =	{Keywords: matroids, matroid intersection, congruency constraint, exact-weight constraint, additive combinatorics, algebraic algorithm, strongly base orderability}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.SAND.2024.3
Algorithmic Programmable Matter: From Local Markov Chains to "Dumb" Robots (Invited Talk)

Authors: Andréa Werneck Richa

Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)

Abstract
Many programmable matter systems have been developed, including modular and swarm robotics, synthetic biology, DNA tiling, and smart materials. We describe programmable matter as an abstract collection of simple computational elements (particles) with limited memory that each execute distributed, local algorithms to self-organize and solve system-wide problems, such as movement, reconfiguration, and coordination. Self-organizing particle systems (SOPS) have many interesting potential applications like coating objects for monitoring and repair purposes, and forming nano-scale devices for surgery and molecular-scale electronic structures. We describe some of our work on the algorithmic foundations of programmable matter, investigating how macro-scale system behaviors can naturally emerge from local micro-behaviors by individual particles: We utilize tools from statistical physics and Markov chain analysis to translate Markov chains defined at a system level into distributed, local algorithms for SOPS that drive the desired emergent collective behavior for the problems of compression, separation, and foraging, among others. We further establish the notion of algorithmic matter, where we leverage standard binary computation, as well as physical characteristics of the robots and interactions with the environment in order to implement our micro-level algorithms in actual testbeds composed of robots that are not capable of any standard computation. We conclude by addressing full concurrency and asynchrony in SOPS. This is joint work with Dana Randall and Dan Goldman (Georgia Tech), Michael Strano (MIT), Todd Murphey (Northwestern), Josh Daymude (Arizona State University), Sarah Cannon (Claremont McKenna), Christian Scheideler (University of Paderborn) and their research labs.
Cite as

Andréa Werneck Richa. Algorithmic Programmable Matter: From Local Markov Chains to "Dumb" Robots (Invited Talk). In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{richa:LIPIcs.SAND.2024.3,
  author =	{Richa, Andr\'{e}a Werneck},
  title =	{{Algorithmic Programmable Matter: From Local Markov Chains to "Dumb" Robots}},
  booktitle =	{3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)},
  pages =	{3:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-315-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{292},
  editor =	{Casteigts, Arnaud and Kuhn, Fabian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.3},
  URN =		{urn:nbn:de:0030-drops-198811},
  doi =		{10.4230/LIPIcs.SAND.2024.3},
  annote =	{Keywords: Programmable matter, Self-organizing particle systems, Biologically-inspired distributed algorithms, Local Markov chains, Emergent collective behavior}
}
Document
DOI: 10.4230/LIPIcs.SAND.2023.6
Adaptive Collective Responses to Local Stimuli in Anonymous Dynamic Networks

Authors: Shunhao Oh, Dana Randall, and Andréa W. Richa

Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)

Abstract
We develop a framework for self-induced phase changes in programmable matter in which a collection of agents with limited computational and communication capabilities can collectively perform appropriate global tasks in response to local stimuli that dynamically appear and disappear. Agents reside on graph vertices, where each stimulus is only recognized locally, and agents communicate via token passing along edges to alert other agents to transition to an Aware state when stimuli are present and an Unaware state when the stimuli disappear. We present an Adaptive Stimuli Algorithm that is robust to competing waves of messages as multiple stimuli change, possibly adversarially. Moreover, in addition to handling arbitrary stimulus dynamics, the algorithm can handle agents reconfiguring the connections (edges) of the graph over time in a controlled way. As an application, we show how this Adaptive Stimuli Algorithm on reconfigurable graphs can be used to solve the foraging problem, where food sources may be discovered, removed, or shifted at arbitrary times. We would like the agents to consistently self-organize, using only local interactions, such that if the food remains in a position long enough, the agents transition to a gather phase in which many collectively form a single large component with small perimeter around the food. Alternatively, if no food source has existed recently, the agents should undergo a self-induced phase change and switch to a search phase in which they distribute themselves randomly throughout the lattice region to search for food. Unlike previous approaches to foraging, this process is indefinitely repeatable, withstanding competing waves of messages that may interfere with each other. Like a physical phase change, microscopic changes such as the deletion or addition of a single food source trigger these macroscopic, system-wide transitions as agents share information about the environment and respond locally to get the desired collective response.
Cite as

Shunhao Oh, Dana Randall, and Andréa W. Richa. Adaptive Collective Responses to Local Stimuli in Anonymous Dynamic Networks. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{oh_et_al:LIPIcs.SAND.2023.6,
  author =	{Oh, Shunhao and Randall, Dana and Richa, Andr\'{e}a W.},
  title =	{{Adaptive Collective Responses to Local Stimuli in Anonymous Dynamic Networks}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{6:1--6:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-275-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{257},
  editor =	{Doty, David and Spirakis, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.6},
  URN =		{urn:nbn:de:0030-drops-179424},
  doi =		{10.4230/LIPIcs.SAND.2023.6},
  annote =	{Keywords: Dynamic networks, adaptive stimuli, foraging, self-organizing particle systems, programmable matter}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2022.51
Brief Announcement: Foraging in Particle Systems via Self-Induced Phase Changes

Authors: Shunhao Oh, Dana Randall, and Andréa W. Richa

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
The foraging problem asks how a collective of particles with limited computational, communication and movement capabilities can autonomously compress around a food source and disperse when the food is depleted or shifted, which may occur at arbitrary times. We would like the particles to iteratively self-organize, using only local interactions, to correctly gather whenever a food particle remains in a position long enough and search if no food particle has existed recently. Unlike previous approaches, these search and gather phases should be self-induced so as to be indefinitely repeatable as the food evolves, with microscopic changes to the food triggering macroscopic, system-wide phase transitions. We present a stochastic foraging algorithm based on a phase change in the fixed magnetization Ising model from statistical physics: Our algorithm is the first to leverage self-induced phase changes as an algorithmic tool. A key component of our algorithm is a careful token passing mechanism ensuring a dispersion broadcast wave will always outpace a compression wave.
Cite as

Shunhao Oh, Dana Randall, and Andréa W. Richa. Brief Announcement: Foraging in Particle Systems via Self-Induced Phase Changes. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 51:1-51:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{oh_et_al:LIPIcs.DISC.2022.51,
  author =	{Oh, Shunhao and Randall, Dana and Richa, Andr\'{e}a W.},
  title =	{{Brief Announcement: Foraging in Particle Systems via Self-Induced Phase Changes}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{51:1--51:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.51},
  URN =		{urn:nbn:de:0030-drops-172423},
  doi =		{10.4230/LIPIcs.DISC.2022.51},
  annote =	{Keywords: Foraging, self-organized particle systems, compression, phase changes}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.14
Local Stochastic Algorithms for Alignment in Self-Organizing Particle Systems

Authors: Hridesh Kedia, Shunhao Oh, and Dana Randall

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Abstract
We present local distributed, stochastic algorithms for alignment in self-organizing particle systems (SOPS) on two-dimensional lattices, where particles occupy unique sites on the lattice, and particles can make spatial moves to neighboring sites if they are unoccupied. Such models are abstractions of programmable matter, composed of individual computational particles with limited memory, strictly local communication abilities, and modest computational capabilities. We consider oriented particle systems, where particles are assigned a vector pointing in one of q directions, and each particle can compute the angle between its direction and the direction of any neighboring particle, although without knowledge of global orientation with respect to a fixed underlying coordinate system. Particles move stochastically, with each particle able to either modify its direction or make a local spatial move along a lattice edge during a move. We consider two settings: (a) where particle configurations must remain simply connected at all times and (b) where spatial moves are unconstrained and configurations can disconnect. Our algorithms are inspired by the Potts model and its planar oriented variant known as the planar Potts model or clock model from statistical physics. We prove that for any q ≥ 2, by adjusting a single parameter, these self-organizing particle systems can be made to collectively align along a single dominant direction (analogous to a solid or ordered state) or remain non-aligned, in which case the fraction of particles oriented along any direction is nearly equal (analogous to a gaseous or disordered state). In the connected SOPS setting, we allow for two distinct parameters, one controlling the ferromagnetic attraction between neighboring particles (regardless of orientation) and the other controlling the preference of neighboring particles to align. We show that with appropriate settings of the input parameters, we can achieve compression and expansion, controlling how tightly gathered the particles are, as well as alignment or nonalignment, producing a single dominant orientation or not. While alignment is known for the Potts and clock models at sufficiently low temperatures, our proof in the SOPS setting are significantly more challenging because the particles make spatial moves, not all sites are occupied, and the total number of particles is fixed.
Cite as

Hridesh Kedia, Shunhao Oh, and Dana Randall. Local Stochastic Algorithms for Alignment in Self-Organizing Particle Systems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 14:1-14:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kedia_et_al:LIPIcs.APPROX/RANDOM.2022.14,
  author =	{Kedia, Hridesh and Oh, Shunhao and Randall, Dana},
  title =	{{Local Stochastic Algorithms for Alignment in Self-Organizing Particle Systems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{14:1--14:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.14},
  URN =		{urn:nbn:de:0030-drops-171367},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.14},
  annote =	{Keywords: Self-organizing particle systems, alignment, Markov chains, active matter}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.3
Iterated Decomposition of Biased Permutations via New Bounds on the Spectral Gap of Markov Chains

Authors: Sarah Miracle, Amanda Pascoe Streib, and Noah Streib

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Abstract
In this paper, we address a conjecture of Fill [Fill03] about the spectral gap of a nearest-neighbor transposition Markov chain ℳ_nn over biased permutations of [n]. Suppose we are given a set of input probabilities 𝒫 = {p_{i,j}} for all 1 ≤ i, j ≤ n with p_{i, j} = 1-p_{j, i}. The Markov chain ℳ_nn operates by uniformly choosing a pair of adjacent elements, i and j, and putting i ahead of j with probability p_{i,j} and j ahead of i with probability p_{j,i}, independent of their current ordering. We build on previous work [S. Miracle and A.P. Streib, 2018] that analyzed the spectral gap of ℳ_nn when the particles in [n] fall into k classes. There, the authors iteratively decomposed ℳ_nn into simpler chains, but incurred a multiplicative penalty of n^-2 for each application of the decomposition theorem of [Martin and Randall, 2000], leading to an exponentially small lower bound on the gap. We make progress by introducing a new complementary decomposition theorem. We introduce the notion of ε-orthogonality, and show that for ε-orthogonal chains, the complementary decomposition theorem may be iterated O(1/√ε) times while only giving away a constant multiplicative factor on the overall spectral gap. We show the decomposition given in [S. Miracle and A.P. Streib, 2018] of a related Markov chain ℳ_pp over k-class particle systems is 1/n²-orthogonal when the number of particles in each class is at least C log n, where C is a constant not depending on n. We then apply the complementary decomposition theorem iteratively n times to prove nearly optimal bounds on the spectral gap of ℳ_pp and to further prove the first inverse-polynomial bound on the spectral gap of ℳ_nn when k is as large as Θ(n/log n). The previous best known bound assumed k was at most a constant.
Cite as

Sarah Miracle, Amanda Pascoe Streib, and Noah Streib. Iterated Decomposition of Biased Permutations via New Bounds on the Spectral Gap of Markov Chains. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 3:1-3:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{miracle_et_al:LIPIcs.APPROX/RANDOM.2020.3,
  author =	{Miracle, Sarah and Streib, Amanda Pascoe and Streib, Noah},
  title =	{{Iterated Decomposition of Biased Permutations via New Bounds on the Spectral Gap of Markov Chains}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{3:1--3:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.3},
  URN =		{urn:nbn:de:0030-drops-126069},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.3},
  annote =	{Keywords: Markov chains, Permutations, Decomposition, Spectral Gap, Iterated Decomposition}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2020.1
Statistical Physics and Algorithms (Invited Talk)

Authors: Dana Randall

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
The field of randomized algorithms has benefitted greatly from insights from statistical physics. We give examples in two distinct settings. The first is in the context of Markov chain Monte Carlo algorithms, which have become ubiquitous across science and engineering as a means of exploring large configuration spaces. One of the most striking discoveries was the realization that many natural Markov chains undergo phase transitions, whereby they are efficient for some parameter settings and then suddenly become inefficient as a parameter of the system is slowly modified. The second is in the context of distributed algorithms for programmable matter. Self-organizing particle systems based on statistical models with phase changes have been used to achieve basic tasks involving coordination, movement, and conformation in a fully distributed, local setting. We briefly describe these two settings to demonstrate how computing and statistical physics together provide powerful insights that apply across multiple domains.
Cite as

Dana Randall. Statistical Physics and Algorithms (Invited Talk). In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 1:1-1:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{randall:LIPIcs.STACS.2020.1,
  author =	{Randall, Dana},
  title =	{{Statistical Physics and Algorithms}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{1:1--1:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.1},
  URN =		{urn:nbn:de:0030-drops-118624},
  doi =		{10.4230/LIPIcs.STACS.2020.1},
  annote =	{Keywords: Markov chains, mixing times, phase transitions, programmable matter}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.37
Slow Mixing of Glauber Dynamics for the Six-Vertex Model in the Ordered Phases

Authors: Matthew Fahrbach and Dana Randall

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
The six-vertex model in statistical physics is a weighted generalization of the ice model on Z^2 (i.e., Eulerian orientations) and the zero-temperature three-state Potts model (i.e., proper three-colorings). The phase diagram of the model represents its physical properties and suggests where local Markov chains will be efficient. In this paper, we analyze the mixing time of Glauber dynamics for the six-vertex model in the ordered phases. Specifically, we show that for all Boltzmann weights in the ferroelectric phase, there exist boundary conditions such that local Markov chains require exponential time to converge to equilibrium. This is the first rigorous result bounding the mixing time of Glauber dynamics in the ferroelectric phase. Our analysis demonstrates a fundamental connection between correlated random walks and the dynamics of intersecting lattice path models (or routings). We analyze the Glauber dynamics for the six-vertex model with free boundary conditions in the antiferroelectric phase and significantly extend the region for which local Markov chains are known to be slow mixing. This result relies on a Peierls argument and novel properties of weighted non-backtracking walks.
Cite as

Matthew Fahrbach and Dana Randall. Slow Mixing of Glauber Dynamics for the Six-Vertex Model in the Ordered Phases. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{fahrbach_et_al:LIPIcs.APPROX-RANDOM.2019.37,
  author =	{Fahrbach, Matthew and Randall, Dana},
  title =	{{Slow Mixing of Glauber Dynamics for the Six-Vertex Model in the Ordered Phases}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{37:1--37:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.37},
  URN =		{urn:nbn:de:0030-drops-112523},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.37},
  annote =	{Keywords: Correlated random walk, Markov chain Monte Carlo, Six-vertex model}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.54
A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems

Authors: Sarah Cannon, Joshua J. Daymude, Cem Gökmen, Dana Randall, and Andréa W. Richa

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
We present and rigorously analyze the behavior of a distributed, stochastic algorithm for separation and integration in self-organizing particle systems, an abstraction of programmable matter. Such systems are composed of individual computational particles with limited memory, strictly local communication abilities, and modest computational power. We consider heterogeneous particle systems of two different colors and prove that these systems can collectively separate into different color classes or integrate, indifferent to color. We accomplish both behaviors with the same fully distributed, local, stochastic algorithm. Achieving separation or integration depends only on a single global parameter determining whether particles prefer to be next to other particles of the same color or not; this parameter is meant to represent external, environmental influences on the particle system. The algorithm is a generalization of a previous distributed, stochastic algorithm for compression (PODC '16) that can be viewed as a special case of separation where all particles have the same color. It is significantly more challenging to prove that the desired behavior is achieved in the heterogeneous setting, however, even in the bichromatic case we focus on. This requires combining several new techniques, including the cluster expansion from statistical physics, a new variant of the bridging argument of Miracle, Pascoe and Randall (RANDOM '11), the high-temperature expansion of the Ising model, and careful probabilistic arguments.
Cite as

Sarah Cannon, Joshua J. Daymude, Cem Gökmen, Dana Randall, and Andréa W. Richa. A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 54:1-54:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{cannon_et_al:LIPIcs.APPROX-RANDOM.2019.54,
  author =	{Cannon, Sarah and Daymude, Joshua J. and G\"{o}kmen, Cem and Randall, Dana and Richa, Andr\'{e}a W.},
  title =	{{A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{54:1--54:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.54},
  URN =		{urn:nbn:de:0030-drops-112696},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.54},
  annote =	{Keywords: Markov chains, Programmable matter, Cluster expansion}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.24
Slow Convergence of Ising and Spin Glass Models with Well-Separated Frustrated Vertices

Authors: David Gillman and Dana Randall

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract
Many physical models undergo phase transitions as some parameter of the system is varied. This phenomenon has bearing on the convergence times for local Markov chains walking among the configurations of the physical system. One of the most basic examples of this phenomenon is the ferromagnetic Ising model on an n x n square lattice region Lambda with mixed boundary conditions. For this spin system, if we fix the spins on the top and bottom sides of the square to be + and the left and right sides to be -, a standard Peierls argument based on energy shows that below some critical temperature t_c, any local Markov chain M requires time exponential in n to mix. Spin glasses are magnetic alloys that generalize the Ising model by specifying the strength of nearest neighbor interactions on the lattice, including whether they are ferromagnetic or antiferromagnetic. Whenever a face of the lattice is bounded by an odd number of edges with ferromagnetic interactions, the face is considered frustrated because the local competing objectives cannot be simultaneously satisfied. We consider spin glasses with exactly four well-separated frustrated faces that are symmetric around the center of the lattice region under 90 degree rotations. We show that local Markov chains require exponential time for all spin glasses in this class. This class includes the ferromagnetic Ising model with mixed boundary conditions described above, where the frustrated faces are on the boundary. The standard Peierls argument breaks down when the frustrated faces are on the interior of Lambda and yields weaker results when they are on the boundary of Lambda but not near the corners. We show that there is a universal temperature T below which M will be slow for all spin glasses with four well-separated frustrated faces. Our argument shows that there is an exponentially small cut indicated by the free energy, carefully exploiting both entropy and energy to establish a small bottleneck in the state space to establish slow mixing.
Cite as

David Gillman and Dana Randall. Slow Convergence of Ising and Spin Glass Models with Well-Separated Frustrated Vertices. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gillman_et_al:LIPIcs.AofA.2018.24,
  author =	{Gillman, David and Randall, Dana},
  title =	{{Slow Convergence of Ising and Spin Glass Models with Well-Separated Frustrated Vertices}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{24:1--24:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.24},
  URN =		{urn:nbn:de:0030-drops-89170},
  doi =		{10.4230/LIPIcs.AofA.2018.24},
  annote =	{Keywords: Mixing time, spin glass, Ising model, mixed boundary conditions, frustration}
}
  • Refine by Author
  • 8 Randall, Dana
  • 3 Oh, Shunhao
  • 3 Richa, Andréa W.
  • 1 Baraskar, Omkar
  • 1 Bojikian, Narek
  • Show More...

  • Refine by Classification
  • 9 Theory of computation → Random walks and Markov chains
  • 6 Theory of computation → Self-organization
  • 3 Mathematics of computing → Stochastic processes
  • 1 Mathematics of computing → Matroids and greedoids
  • 1 Theory of computation → Algebraic complexity theory
  • Show More...

  • Refine by Keyword
  • 5 Markov chains
  • 3 programmable matter
  • 2 Programmable matter
  • 2 Self-organizing particle systems
  • 2 phase transitions
  • Show More...

  • Refine by Type
  • 16 document

  • Refine by Publication Year
  • 7 2024
  • 2 2019
  • 2 2020
  • 2 2022
  • 1 2017
  • Show More...

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact