An official website of the United States government
Memristor devices have been extensively studied as one of the most promising technologies for next-generation non-volatile memory. However, for the memristor devices to have a real technological impact, they must be densely packed in a large crossbar array (CBA) exceeding Gigabytes in size. Devising a selector device that is CMOS compatible, 3D stackable, and has a high non-linearity (NL) and great endurance is a crucial enabling ingredient to reach this goal. Tunneling based selectors are very promising in these aspects, but the mediocre NL value limits their applications in large passive crossbar arrays. In this work, we demonstrated a trilayer tunneling selector based on the Ge/Pt/TaN 1+x /Ta 2 O 5 /TaN 1+x /Pd layers that could achieve a NL of 3 × 10 5 , which is the highest NL achieved using a tunnel selector so far. The record-high tunneling NL is partially attributed to the bottom electrode's ultra-smoothness (BE) induced by a Ge/Pt layer. We further demonstrated the feasibility of 1S1R (1-selector 1-resistor) integration by vertically integrating a Pd/Ta 2 O 5 /Ru based memristor on top of the proposed selector.
more »
« less
This content will become publicly available on December 27, 2025
On Permutation Selectors and their Applications in Ad-Hoc Radio Networks Protocols
Selective families of sets, or selectors, are combinatorial tools used to “isolate” individual members of sets from some set family. Given a set X and an element x ∈ X, to isolate x from X, at least one of the sets in the selector must intersect X on exactly x. We study (k,N)-permutation selectors which have the property that they can isolate each element of each k-element subset of {0, 1, ..., N − 1} in each possible order. These selectors can be used in protocols for ad-hoc radio networks to more efficiently disseminate informa- tion along multiple hops. In 2004, Gasieniec, Radzik and Xin gave a construc- tion of a (k, N )-permutation selector of size O(k2 log3 N ). This paper improves this by providing a probabilistic construction of a (k, N )-permutation selector of size O(k2 log N ). Remarkably, this matches the asymptotic bound for standard strong (k,N)-selectors, that isolate each element of each set of size k, but with no restriction on the order. We then show that the use of our (k, N )-permutation selector improves the best running time for gossiping in ad-hoc radio networks by a poly-logarithmic factor.
more »
« less
- Award ID(s):
- 2153723
- PAR ID:
- 10598869
- Editor(s):
- Bramas, Quentin; Casteigts, Arnaud; Meeks, Kitty
- Publisher / Repository:
- Springer Nature Switzerland
- Date Published:
- ISSN:
- 0302-9743
- ISBN:
- 978-3-031-74579-9
- Page Range / eLocation ID:
- 106 to 116
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Keil, Mark; Mondal, Debajyoti (Ed.)We adapt and generalize a heuristic for k-center clustering to the permutation case, where every pre x of the ordering is a guaranteed approximate solution. The one-hop greedy permutations work by choosing at each step the farthest unchosen point and then looking in its local neighborhood for a point that covers the most points at a certain scale. This balances the competing demands of reducing the coverage radius and also covering as many points as possible. This idea first appeared in the work of Garcia-Diaz et al. and their algorithm required O(n2 log n) time for a fi xed k (i.e. not the whole permutation). We show how to use geometric data structures to approximate the entire permutation in O(n log D) time for metrics sets with spread D. Notably, this running time is asymptotically the same as the running time for computing the ordinary greedy permutation.more » « less
-
Set representation has become ubiquitous in deep learning for modeling the inductive bias of neural networks that are insensitive to the input order. DeepSets is the most widely used neural network architecture for set representation. It involves embedding each set element into a latent space with dimension L, followed by a sum pooling to obtain a whole-set embedding, and finally mapping the whole-set embedding to the output. In this work, we investigate the impact of the dimension L on the expressive power of DeepSets. Previous analyses either oversimplified high-dimensional features to be one-dimensional features or were limited to analytic activations, thereby diverging from practical use or resulting in L that grows exponentially with the set size N and feature dimension D. To investigate the minimal value of L that achieves sufficient expressive power, we present two set-element embedding layers: (a) linear + power activation (LP) and (b) linear + exponential activations (LE). We demonstrate that L being poly(N,D) is sufficient for set representation using both embedding layers. We also provide a lower bound of L for the LP embedding layer. Furthermore, we extend our results to permutation-equivariant set functions and the complex field.more » « less
-
We present efficient dynamic data structures for maintaining the union of unit discs and the lower envelope of pseudo-lines in the plane. More precisely, we present three main results in this paper: (i) We present a linear-size data structure to maintain the union of a set of unit discs under insertions. It can insert a disc and update the union in O (( k +1)log 2 n ) time, where n is the current number of unit discs and k is the combinatorial complexity of the structural change in the union due to the insertion of the new disc. It can also compute, within the same time bound, the area of the union after the insertion of each disc. (ii) We propose a linear-size data structure for maintaining the lower envelope of a set of x -monotone pseudo-lines. It can handle insertion/deletion of a pseudo-line in O (log 2 n ) time; for a query point x 0 ∈ ℝ, it can report, in O (log n ) time, the point on the lower envelope with x -coordinate x 0 ; and for a query point q ∈ ℝ 2 , it can return all k pseudo-lines lying below q in time O (log n + k log 2 n ). (iii) We present a linear-size data structure for storing a set of circular arcs of unit radius (not necessarily on the boundary of the union of the corresponding discs), so that for a query unit disc D , all input arcs intersecting D can be reported in O ( n 1/2+ɛ + k ) time, where k is the output size and ɛ > 0 is an arbitrarily small constant. A unit-circle arc can be inserted or deleted in O (log 2 n ) time.more » « less
-
null (Ed.)Given an element set E of order n, a collection of subsets [Formula: see text], a cost c S on each set [Formula: see text], a covering requirement r e for each element [Formula: see text], and an integer k, the goal of a minimum partial set multicover problem (MinPSMC) is to find a subcollection [Formula: see text] to fully cover at least k elements such that the cost of [Formula: see text] is as small as possible and element e is fully covered by [Formula: see text] if it belongs to at least r e sets of [Formula: see text]. This problem generalizes the minimum k-union problem (MinkU) and is believed not to admit a subpolynomial approximation ratio. In this paper, we present a [Formula: see text]-approximation algorithm for MinPSMC, in which [Formula: see text] is the maximum size of a set in S. And when [Formula: see text], we present a bicriteria algorithm fully covering at least [Formula: see text] elements with approximation ratio [Formula: see text], where [Formula: see text] is a fixed number. These results are obtained by studying the minimum density subcollection problem with (or without) cardinality constraint, which might be of interest by itself.more » « less
