More Like this

1. Transverse Wave Propagation Bandgap in a Buckled Kirigami Sheet

   https://doi.org/10.1115/SMASIS2021-68200  

   Khosravi, Hesameddin; Li, Suyi (September 2021, Proceedings of the ASME 2021 Conference on Smart Materials, Adaptive Structures and Intelligent Systems)

   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 in-plane stretching force that exceeds a critical threshold, this kirigami sheet buckles and generates an out-of-plane, 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 out-of-plane 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 multi-functional structural system. 

   more » « less
2. Multi-position metamaterial switch enables adjustable bandgaps for guiding elastic waves

   https://doi.org/10.1063/5.0256329  

   Kheybari, Majid; Xu, Hongyi (August 2025, AIP Advances)

   In this paper, we present a computational investigation into the dynamic behavior of a tunable multi-position metamaterial switch. We examine the dynamical characteristics of the metamaterial switch, which can transition between positions ranging from state 0 to state 5. Each state corresponds to fixed, stable bandgaps, and the switch does not require external stimuli to maintain its properties. By adjusting the position of the switch, we can effectively modify the location of complete bandgaps, allowing for precise control over the propagation of elastic waves. We demonstrate the utility of the proposed metamaterial switch by enabling wave-guiding capabilities and achieving tunable multiplexing across different frequencies. In addition, we expand the analysis by combining multiple unit cells into supercells with varying configurations, enabling further tuning of dispersion characteristics and bandgap properties. The presented design principles can be applied to various applications in elastic wave manipulation and vibration isolation. 

   more » « less
3. Explicit two-source extractors and resilient functions

   Chattopadhyay, E; Zuckerman, D (May 2019, Annals of mathematics)

   We explicitly construct an extractor for two independent sources on n bits, each with min-entropy at least log^C n for a large enough constant C. Our extractor outputs one bit and has error n^{-\Omega(1)}. The best previous extractor, by Bourgain, required each source to have min-entropy .499n. A key ingredient in our construction is an explicit construction of a monotone, almost-balanced boolean function on n bits that is resilient to coalitions of size n^{1-delta}, for any delta>0. In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on n bits, where some unknown n-q bits are chosen almost polylog(n)-wise independently, and the remaining q=n^{1-\delta} bits are chosen by an adversary as an arbitrary function of the n-q bits. The best previous construction, by Viola, achieved q=n^{1/2 - \delta}. Our explicit two-source extractor directly implies an explicit construction of a 2^{(log log N)^{O(1)}}-Ramsey graph over N vertices, improving bounds obtained by Barak et al. and matching independent work by Cohen. 

   more » « less
4. Fully Functional Parameterized Suffix Trees in Compact Space

   Ganguly, Arnab; Shah, Rahul; Thankachan, Sharma V. (June 2022, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022))

   Mikolaj Bojanczyk; Emanuela Merelli; David P. Woodruff (Ed.)

   Two equal length strings are a parameterized match (p-match) iff there exists a one-to-one 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+|P|-1] and P are a p-match. The PST can count the number of occurrences of P in T in time O(|P|log σ) 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 trade-off is an improvement over Ganguly et al.’s result, whereas our third trade-off matches the optimal time performance of Baker’s PST while squeezing the space by a factor roughly log_σ n. We highlight that our trade-offs match the space-and-time bounds of the best-known compressed text indexes for exact pattern matching and further improvement is highly unlikely. 

   more » « less
5. Tiny Pointers

   Michael A. Bender; Alex Conway; Martín Farach-Colton; William Kuszmaul; Guido Tagliavini (January 2023, Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA))

   This paper introduces a new data-structural object that we call the tiny pointer. In many applications, traditional log n-bit pointers can be replaced with o(log n)-bit tiny pointers at the cost of only a constant-factor time overhead and a small probability of failure. We develop a comprehensive theory of tiny pointers, and give optimal constructions for both fixed-size tiny pointers (i.e., settings in which all of the tiny pointers must be the same size) and variable-size tiny pointers (i.e., settings in which the average tiny-pointer 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 tiny-pointer size is Θ(log log log n + log δ-1) bits in the fixed-size case, and Θ(log δ-1) expected bits in the variable-size case. Our tiny-pointer 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 data-structure problems. We show that: • A data structure storing n v-bit values for n keys with constant-time 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 r-th iterated logarithm. • Any binary search tree can be made succinct with constant-factor 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 rotation-based trees such as the splay tree and the red-black tree. • Any fixed-capacity key-value dictionary can be made stable (i.e., items do not move once inserted) with constant-time overhead and 1 + o(1) space overhead. • Any key-value dictionary that requires uniform-size values can be made to support arbitrary-size values with constant-time overhead and with an additional space consumption of log(r) n + O(log j) bits per j-bit value for an arbitrary constant r > 0 of our choice. • Given an external-memory array A of size (1 + ε)n containing a dynamic set of up to n key-value pairs, it is possible to maintain an internal-memory stash of size O(n log ε-1) bits so that the location of any key-value 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 space-inefficient solution that uses pointers and make it space-efficient for free. 

   more » « less