196,686 research outputs found
Near-Optimal Hypergraph Sparsification in Insertion-Only and Bounded-Deletion Streams
No full textWe study the problem of constructing hypergraph cut sparsifiers in the streaming model where a hypergraph on n vertices is revealed either via an arbitrary sequence of hyperedge insertions alone (insertion-only streaming model) or via an arbitrary sequence of hyperedge insertions and deletions (dynamic streaming model). For any ε ∈ (0,1), a (1 ± ε) hypergraph cut-sparsifier of a hypergraph H is a reweighted subgraph H' whose cut values approximate those of H to within a (1 ± ε) factor. Prior work shows that in the static setting, one can construct a (1 ± ε) hypergraph cut-sparsifier using Õ(nr/ε²) bits of space [Chen-Khanna-Nagda FOCS 2020], and in the setting of dynamic streams using Õ(nrlog m/ε²) bits of space [Khanna-Putterman-Sudan FOCS 2024]; here the Õ notation hides terms that are polylogarithmic in n, and we use m to denote the total number of hyperedges in the hypergraph. Up until now, the best known space complexity for insertion-only streams has been the same as that for the dynamic streams. This naturally poses the question of understanding the complexity of hypergraph sparsification in insertion-only streams.
Perhaps surprisingly, in this work we show that in insertion-only streams, a (1 ± ε) cut-sparsifier can be computed in Õ(nr/ε²) bits of space, matching the complexity of the static setting. As a consequence, this also establishes an Ω(log m) factor separation between the space complexity of hypergraph cut sparsification in insertion-only streams and dynamic streams, as the latter is provably known to require Ω(nr log m) bits of space. To better explain this gap, we then show a more general result: namely, if the stream has at most k hyperedge deletions then Õ(n r log k/ε²) bits of space suffice for hypergraph cut sparsification. Thus the space complexity smoothly interpolates between the insertion-only regime (k = 0) and the fully dynamic regime (k = m). Our algorithmic results are driven by a key technical insight: once sufficiently many hyperedges have been inserted into the stream (relative to the number of allowed deletions), we can significantly reduce the underlying hypergraph by size by irrevocably contracting large subsets of vertices.
Finally, we complement this result with an essentially matching lower bound of Ω(n r log(k/n)) bits, thus providing essentially a tight characterization of the space complexity for hypergraph cut-sparsification across a spectrum of streaming models
Pseudorandom Linear Codes Are List-Decodable to Capacity
No full textWe introduce a novel family of expander-based error correcting codes. These codes can be sampled with randomness linear in the block-length, and achieve list decoding capacity (among other local properties). Our expander-based codes can be made starting from any family of sufficiently low-bias codes, and as a consequence, we give the first construction of a family of algebraic codes that can be sampled with linear randomness and achieve list-decoding capacity. We achieve this by introducing the notion of a pseudorandom puncturing of a code, where we select n indices of a base code C ⊂ _q^m in a correlated fashion. Concretely, whereas a random linear code (i.e. a truly random puncturing of the Hadamard code) requires O(n log(m)) random bits to sample, we sample a pseudorandom linear code with O(n + log (m)) random bits by instantiating our pseudorandom puncturing as a length n random walk on an exapnder graph on [m]. In particular, we extend a result of Guruswami and Mosheiff (FOCS 2022) and show that a pseudorandom puncturing of a small-bias code satisfies the same local properties as a random linear code with high probability. As a further application of our techniques, we also show that pseudorandom puncturings of Reed-Solomon codes are list-recoverable beyond the Johnson bound, extending a result of Lund and Potukuchi (RANDOM 2020). We do this by instead analyzing properties of codes with large distance, and show that pseudorandom puncturings still work well in this regime
Lavish Returns on Cheap Talk: Non-binding Communication in a Trust Experiment
No full textWe let subjects interact with anonymous partners in trust (investment) games with and without one of two kinds of pre-play communication: numerical (tabular) only, and verbal and numerical. We find that either kind of pre-play communication increases trusting, trustworthiness, or both, in inter-subject comparisons, but that the inclusions of verbal communication generates both a larger effect and one that is robust across both inter-subject and intra-subject comparisons. In all conditions, trustors earn more when they invest more of their endowment, trustors and trustees gravitate to "fair and efficient" interactions, and the majority of trustees adhere to their commitments, whether explicit or implicit. Finally, we study trusting and trustworthiness in the sense of adhering to agreements, and we find that both are enhanced when the parties can use words, and especially when an agreement is reached with words and not only with the exchange of numerical proposals.
Commentary on: Modified Levator Muscle Resection Using Putterman Müller’s Muscle-Conjunctival Resection-Ptosis Clamp
No full textOn the -Order Weighted Projection Body Operator and Related Inequalities
No full textFor a convex body in , the inequalities of Rogers-Shephard
and Zhang, written succinctly, are Here,
is the difference body of
, and is the polar projection body of . There is equality
in either if, and only if, is a -dimensional simplex. In fact, there
exists a collection of convex bodies, the so-called radial mean bodies
introduced by Gardner and Zhang, which continuously interpolates between
and . For , Schneider defined the th-order
difference body of as and proved
the th-order Rogers-Shephard inequality. In a prequel to this work, the
authors, working with Haddad, extended this th-order concept to the radial
mean bodies and the polar projection body, establishing the associated Zhang's
projection inequality.
In this work, we introduce weighted versions of the above-mentioned operators
by replacing the Lebesgue measure with measures that have density. The weighted
version of these operators in the case was first done by Roysdon
(difference body), Langharst-Roysdon-Zvavitch (polar projection body) and
Langharst-Putterman (radial mean bodies). This work can be seen as a sequel to
all those works, extending them to th-order. In the last section, we extend
many of these ideas to the setting of generalized volume, first introduced by
Gardner-Hug-Weil-Xing-Ye.Comment: 33 pages, Keywords: Projection Bodies, Rogers-Shephard Inequality,
Zhang's Inequality, Radial Mean Bodies. Title changed from "higher-order..."
to "mth order..." Accepted into Pure and Applied Functional Analysis, Special
Issue in honour of Nicole Tomczak-Jaegerman
Dr. Duane M. Jackson, Morehouse College, July 2011
No full textThis video is a conversation with Dr. Duane M. Jackson. Dr. Jackson talks about his paper, "Recall and the Serial Position Effect: The Role of Primacy and Recency on Accounting Students' Performance." Jackie Daniel, AUC Woodruff Library, is the interviewer
"Reflections on the subject of Emigration from Europe with a view to Settlement in the United States" By M. Carey.
No full text"Reflections on the subject of Emigration from Europe with a view to Settlement in the United States: containing bried sketches of the moral and political character of those states.
By M. Carey, member of the American philosophical, and of the American Antiquarian Society, and author of The Olive Branch, Cindiciae Hibernicae, essays on banking, on political economy, and on internal improvement.
To which are now added the English editor's comments on the subject; together with Important Advice to Emigrants, and Cautions Against Impositions Practiced in the Outports
Dispelling the Myths Behind First-author Citation Counts
No full textWe conducted a full-scale evaluative citation analysis study of scholars in the XML research field to explore just how different from each other author rankings resulting from different citation counting methods actually are, and to demonstrate the capability of emerging data and tools on the Web in supporting more realistic citation counting methods. Our results contest some common arguments for the continued
use of first-author citation counts in the evaluation of scholars, such as high correlations between author rankings by first-author citation counts and other citation
counting methods, and high costs of using more realistic citation counting methods that are not well-supported by the ISI databases. It is argued that increasingly available digital full text research papers make it possible for citation analysis studies to go beyond what the ISI databases have directly supported and to employ more
sophisticated methods
- …
