This study investigates the programming of elastic wave propagation bandgaps in periodic and multi‐stable metamaterials by intentionally and uniquely sequencing its constitutive mechanical bits. To this end, stretched kirigami is used as a simple and versatile testing platform. Each mechanical bit in the stretched kirigami can switch between two stable equilibria with different external shapes (aka. “(0)” and “(1)” states). Therefore, by designing the sequence of (0) and (1) bits, one can fundamentally change the underlying periodicity and thus program the phononic bandgap frequencies. This study develops an algorithm to identify the unique periodicities generated by assembling “
 NSFPAR ID:
 10419000
 Publisher / Repository:
 Wiley Blackwell (John Wiley & Sons)
 Date Published:
 Journal Name:
 Advanced Materials Technologies
 Volume:
 8
 Issue:
 13
 ISSN:
 2365709X
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Mikolaj Bojanczyk ; Emanuela Merelli ; David P. Woodruff (Ed.)Two equal length strings are a parameterized match (pmatch) iff there exists a onetoone function that renames the symbols in one string to those in the other. The Parameterized Suffix Tree (PST) [Baker, STOC' 93] is a fundamental data structure that handles various string matching problems under this setting. The PST of a text T[1,n] over an alphabet Σ of size σ takes O(nlog n) bits of space. It can report any entry in (parameterized) (i) suffix array, (ii) inverse suffix array, and (iii) longest common prefix (LCP) array in O(1) time. Given any pattern P as a query, a position i in T is an occurrence iff T[i,i+P1] and P are a pmatch. The PST can count the number of occurrences of P in T in time O(Plog σ) and then report each occurrence in time proportional to that of accessing a suffix array entry. An important question is, can we obtain a compressed version of PST that takes space close to the text’s size of nlogσ bits and still support all three functionalities mentioned earlier? In SODA' 17, Ganguly et al. answered this question partially by presenting an O(nlogσ) bit index that can support (parameterized) suffix array and inverse suffix array operations in O(log n) time. However, the compression of the (parameterized) LCP array and the possibility of faster suffix array and inverse suffix array queries in compact space were left open. In this work, we obtain a compact representation of the (parameterized) LCP array. With this result, in conjunction with three new (parameterized) suffix array representations, we obtain the first set of PST representations in o(nlog n) bits (when logσ = o(log n)) as follows. Here ε > 0 is an arbitrarily small constant.  Space O(n logσ) bits and query time O(log_σ^ε n);  Space O(n logσlog log_σ n) bits and query time O(log log_σ n); and  Space O(n logσ log^ε_σ n) bits and query time O(1). The first tradeoff is an improvement over Ganguly et al.’s result, whereas our third tradeoff matches the optimal time performance of Baker’s PST while squeezing the space by a factor roughly log_σ n. We highlight that our tradeoffs match the spaceandtime bounds of the bestknown compressed text indexes for exact pattern matching and further improvement is highly unlikely.more » « less

This study examines the transverse elastic wave propagation bandgap in a buckled kirigami sheet. Kirigami — the ancient art of paper cutting — has become a design and fabrication framework for constructing metamaterials, robotics, and mechanical devices of vastly different sizes. For the first time, this study focuses on the wave propagation in a buckled kirigami sheet with uniformly distributed parallel cuts. When we apply an inplane stretching force that exceeds a critical threshold, this kirigami sheet buckles and generates an outofplane, periodic deformation pattern that can change the propagation direction of passing waves. That is, waves entering the buckled Kirigami unit cells through its longitudinal direction can turn to the outofplane direction. As a result, the stretched kirigami sheet shows wave propagation band gaps in specific frequency ranges. This study formulates an analytical model to analyze the correlation between such propagation bandgap and the kirigami geometry. This model first simplifies the complex shape of buckled kirigami by introducing “virtual” folds and flat facets in between them. Then it incorporates the plane wave expansion method (PWE) to calculate the dispersion relationship, which shows that the periodic nature of the buckled kirigami sheet is sufficient to create Bragg scattering propagation bandgap. This study’s results could open up new dynamic functionalities of kirigami as a versatile and multifunctional structural system.more » « less

This paper introduces a new datastructural object that we call the tiny pointer. In many applications, traditional log nbit pointers can be replaced with o(log n)bit tiny pointers at the cost of only a constantfactor time overhead and a small probability of failure. We develop a comprehensive theory of tiny pointers, and give optimal constructions for both fixedsize tiny pointers (i.e., settings in which all of the tiny pointers must be the same size) and variablesize tiny pointers (i.e., settings in which the average tinypointer size must be small, but some tiny pointers can be larger). If a tiny pointer references an element in an array filled to load factor 1 — δ, then the optimal tinypointer size is Θ(log log log n + log δ1) bits in the fixedsize case, and Θ(log δ1) expected bits in the variablesize case. Our tinypointer constructions also require us to revisit several classic problems having to do with balls and bins; these results may be of independent interest. Using tiny pointers, we revisit five classic datastructure problems. We show that: • A data structure storing n vbit values for n keys with constanttime modifications/queries can be implemented to take space nv + O(n log(r) n) bits, for any constant r > 0, as long as the user stores a tiny pointer of expected size O(1) with each key—here, log(r) n is the rth iterated logarithm. • Any binary search tree can be made succinct with constantfactor time overhead, and can even be made to be within O(n) bits of optimal if we allow for O(log* n)time modifications—this holds even for rotationbased trees such as the splay tree and the redblack tree. • Any fixedcapacity keyvalue dictionary can be made stable (i.e., items do not move once inserted) with constanttime overhead and 1 + o(1) space overhead. • Any keyvalue dictionary that requires uniformsize values can be made to support arbitrarysize values with constanttime overhead and with an additional space consumption of log(r) n + O(log j) bits per jbit value for an arbitrary constant r > 0 of our choice. • Given an externalmemory array A of size (1 + ε)n containing a dynamic set of up to n keyvalue pairs, it is possible to maintain an internalmemory stash of size O(n log ε1) bits so that the location of any keyvalue pair in A can be computed in constant time (and with no IOs). These are all well studied and classic problems, and in each case tiny pointers allow for us to take a natural spaceinefficient solution that uses pointers and make it spaceefficient for free.more » « less

In this paper, we study the fundamental problem of gossip in the mobile telephone model: a recently introduced variation of the classical telephone model modified to better describe the local peertopeer communication services implemented in many popular smartphone operating systems. In more detail, the mobile telephone model differs from the classical telephone model in three ways: (1) each device can participate in at most one connection per round; (2) the network topology can undergo a parameterized rate of change; and (3) devices can advertise a parameterized number of bits about their state to their neighbors in each round before connection attempts are initiated. We begin by describing and analyzing new randomized gossip algorithms in this model under the harsh assumption of a network topology that can change completely in every round. We prove a significant time complexity gap between the case where nodes can advertise 0 bits to their neighbors in each round, and the case where nodes can advertise 1 bit. For the latter assumption, we present two solutions: the first depends on a shared randomness source, while the second eliminates this assumption using a pseudorandomness generator we prove to exist with a novel generalization of a classical result from the study of twoparty communication complexity. We then turn our attention to the easier case where the topology graph is stable, and describe and analyze a new gossip algorithm that provides a substantial performance improvement for many parameters. We conclude by studying a relaxed version of gossip in which it is only necessary for nodes to each learn a specified fraction of the messages in the system. We prove that our existing algorithms for dynamic network topologies and a single advertising bit solve this relaxed version up to a polynomial factor faster (in network size) for many parameters. These are the first known gossip results for the mobile telephone model, and they significantly expand our understanding of how to communicate and coordinate in this increasingly relevant setting.more » « less

Abstract The bulkboundary correspondence (bbc) principle states that the presence and number of
evanescent bandgap modes at an interface between two periodic media depend on the topological invariants (Chern numbers in 2D or Zak phases in 1D) ofpropagating modesat completely different frequencies in all Bloch bands below that bandgap. The objective of this letter is to explain, on physical grounds, this connection between modes with completely different characteristics. We assume periodic lossless 1D structures and lattice cells with mirror symmetry; in this case the Zak phase is unambiguously defined. The letter presents a systematic study of the behavior of electromagnetic Bloch impedance, defined as the ratio of electrical and magnetic fields in a Bloch wave at the boundary of a lattice cell. The impedancecentric view confers transparent physical meaning on the bulkboundary correspondence principle. Borrowing from the semiconductor terminology, we classify the bandgaps asp  andn type at the Γ andX points, depending on whether the Bloch impedance has a pole (p ) or a null (n ) at the bottom of that gap. An interface mode exists only forpn junctions per our definition. We expect these ideas to be extendable to problems in higher dimensions, with a variety of emerging applications.