检索结果-内蒙古大学图书馆

arXiv 2023年

作者： Fitzsimmons, Zack Hemaspaandra, Edith Dept. of Math. and Computer Science College of the Holy Cross WorcesterMA01610 United States Department of Computer Science Rochester Institute of Technology RochesterNY14623 United States

It is important to study how strategic agents can affect the outcome of an election. There has been a long line of research in the computational study of elections on the complexity of manipulative actions such as manipulation and bribery. These problems model scenarios such as voters casting strategic votes and agents campaigning for voters to change their votes to make a desired candidate win. A common assumption is that the preferences of the voters follow the structure of a domain restriction such as single peakedness, and so manipulators only consider votes that also satisfy this restriction. We introduce the model where the preferences of the voters define their own restriction and strategic actions must "conform" by using only these votes. In this model, the election after manipulation will retain common domain restrictions. We explore the computational complexity of conformant manipulative actions and we discuss how conformant manipulative actions relate to other manipulative actions. Copyright © 2023, The Authors. All rights reserved.

关键词： Machine learning

来源：评论

学校读者我要写书评

暂无评论

Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs

Low Acceptance Agreement Tests via Bounded-Degree Symplectic...

引用

Annual IEEE Symposium on Foundations of computer science

作者： Yotam Dikstein Irit Dinur Alexander Lubotzky Computer Science and Discrete Mathematics Institute for Advanced Study Princeton New Jersey USA Dept. of Applied Math and Computer Science The Weizmann Institute of Science Rehovot Israel Department of Mathematics The Weizmann Institute of Science Rehovot Israel

ISBN: (数字)9798331516741

ISBN: (纸本)9798331516758

We solve the derandomized direct product testing question in the low acceptance regime, by constructing new high dimensional expanders that have no small connected covers. We show that our complexes have swap cocycle expansion, which allows us to deduce the agreement theorem by relying on previous work. Derandomized direct product testing, also known as agreement testing, is the following problem. Let $X$ be a family of k-element subsets of $[N]$ and let $\{f_{s}:s\rightarrow\Sigma\vert s\in X\}$ be an ensemble of local functions, each defined over a subset $s\subset\lceil N$ . Suppose that we run the following so-called agreement test: choose a random pair of sets $s_{1}, s_{2}\in X$ that intersect on $\sqrt{k}$ elements, and accept if $f_{s_{1}}, f_{s_{2}}$ agree on the elements in $s_{1}\cap s_{2}$ . We denote the success probability of this test by Agree $\{f_{s}\})$ Given that Agree $(\{f_{s}\})=\varepsilon > 0$ is there a global function $G:[N]\rightarrow\Sigma$ such that $f_{s}=G\vert _{s}$ for a non-negligible fraction of $s\in X\ ?$ We construct a family $X$ of k-subsets of $[N]$ such that $\vert X\vert =O(N)$ , and such that it satisfies the low acceptance agreement theorem. Namely, $\text{Agree}\left(\left\{f_s\right\}\right)>\varepsilon \Longrightarrow \exists G:[N] \rightarrow \Sigma, \quad \underset{s}{\math.b{P}}\left[\left.f_s \stackrel{0.99}{\approx} G\right\vert_s\right] \geqslant \text{poly}(\varepsilon)$ . A key idea is to replace the well-studied LSV complexes by symplectic high dimensional expanders (HDXs). The family $X$ is just the k-faces of the new symplectic HDXs. The latter serve our needs better since their fundamental group satisfies the congruence subgroup property, which implies that they lack small covers. We also give a polynomial-time algorithm to construct this family of sym-plectic HDXs.

关键词： computer science Testing

来源：评论

学校读者我要写书评

暂无评论

Expansion of high-dimensional cubical complexes with application to quantum locally testable codes

arXiv

引用

arXiv 2024年

作者： Dinur, Irit Lin, Ting-Chun Vidick, Thomas Department of Applied Math and Computer Science The Weizmann Institute of Science Department of Physics University of California San Diego CA United States Hon Hai Research Institute Taipei Taiwan

We introduce a high-dimensional cubical complex, for any dimension t ∈ N, and apply it to the design of quantum locally testable codes. Our complex is a natural generalization of the constructions by Panteleev and Kalachev and by Dinur et. al of a square complex (case t = 2), which have been applied to the design of classical locally testable codes (LTC) and quantum low-density parity check codes (qLDPC) respectively. We turn the geometric (cubical) complex into a chain complex by relying on constant-sized local codes h1, . . . , ht as gadgets. A recent result of Panteleev and Kalachev on existence of tuples of codes that are product expanding enables us to prove lower bounds on the cycle and co-cycle expansion of our chain complex. For t = 4 our construction gives a new family of "almost-good" quantum LTCs — with constant relative rate, inverse-polylogarithmic relative distance and soundness, and constant-size parity checks. Both the distance of the quantum code and its local testability are proven directly from the cycle and co-cycle expansion of our chain complex. Copyright © 2024, The Authors. All rights reserved.

关键词： Expansion

来源：评论

学校读者我要写书评

暂无评论

Graph Fourier MMD for Signals on Graphs

Graph Fourier MMD for Signals on Graphs

引用

2023 International Conference on Sampling Theory and Applications, SampTA 2023

作者： Leone, Samuel Venkat, Aarthi Huguet, Guillaume Tong, Alexander Wolf, Guy Krishnaswamy, Smita Applied Math Program New HavenCT United States Yale University Computational Biology & Bioinformatics Program New HavenCT United States Université de Montréal Mila - Quebec Ai Institute Dept. of Math. & Stat Montreal Canada Université de Montréal Mila-Quebec Ai Institute Dept. of Comp. Sci. & Oper. Res. Montreal Canada Yale University Department of Computer Science Department of Genetics New HavenCT United States

ISBN: (纸本)9798350328851

While numerous methods have been proposed for computing distances between probability distributions in Euclidean space, relatively little attention has been given to computing such distances for distributions on graphs. However, there has been a marked increase in data that either lies on graph (such as protein interaction networks) or can be modeled as a graph (single cell data), particularly in the biomedical sciences. Thus, it becomes important to find ways to compare signals defined on such graphs. Here, we propose Graph Fourier MMD (GFMMD), a novel distance between distributions and signals on graphs. GFMMD is defined via an optimal witness function that is both smooth on the graph and maximizes the difference in expectation between the pair of distributions on the graph. We find an analytical solution to this optimization problem as well as an embedding of distributions that results from this method. We also prove several properties of this method including scale invariance and applicability to disconnected graphs. We showcase it on graph benchmark datasets as well on single cell RNA-sequencing data analysis. In the latter, we use the GFMMD-based gene embeddings to find meaningful gene clusters. We also propose a novel type of score for gene selection called gene localization score which helps select genes for cellular state space characterization. © 2023 IEEE.

关键词： Genes

来源：评论

学校读者我要写书评

暂无评论

Noisy Circumnutations Facilitate Self-Organized Shade Avoidance in Sunflowers

引用

Physical Review X 2024年第3期14卷 031027-031027页

作者： Chantal Nguyen Imri Dromi Ahron Kempinski Gabriella E. C. Gall Orit Peleg Yasmine Meroz BioFrontiers Institute School of Plant Science and Food Security The Center for Physics and Chemistry of Living Systems Zukunftskolleg Department of Biology Centre for the Advanced Study of Collective Behaviour Konstanz Germany Department of Computer Science Department of Physics Department of Applied Math Department of Ecology and Evolutionary Biology Santa Fe New Mexico USA

Circumnutations are widespread in plants and typically associated with exploratory movements; however, a quantitative understanding of their role remains elusive. In this study we report, for the first time, the role of noisy circumnutations in facilitating an optimal growth pattern within a crowded group of mutually shading plants. We revisit the problem of self-organization observed for sunflowers, mediated by shade response interactions. Our analysis reveals that circumnutation movements conform to a bounded random walk characterized by a remarkably broad distribution of velocities, covering 3 orders of magnitude. In motile animal systems such wide distributions of movement velocities are frequently identified with enhancement of behavioral processes, suggesting that circumnutations may serve as a source of functional noise. To test our hypothesis, we developed a Langevin-type parsimonious model of interacting growing disks, informed by experiments, successfully capturing the characteristic dynamics of individual and multiple interacting plants. Employing our simulation framework we examine the role of circumnutations in the system, and find that the observed breadth of the velocity distribution represents a sharp transition in the force-noise ratio, conferring advantageous effects by facilitating exploration of potential configurations, leading to an optimized arrangement with minimal shading. These findings represent the first report of functional noise in plant movements and establish a theoretical foundation for investigating how plants navigate their environment by employing computational processes such as task-oriented processes, optimization, and active sensing. Since plants move by growing, space and time are coupled, and dynamics of self-organization lead to emergent 3D patterns. As such, this system provides conceptual insight for other interacting growth-driven systems such as fungal hyphae, neurons and self-growing robots, as well as active matter sys

关键词： Animal behavior, social interactions & emergent phenomena Biological self-organization Emergence of patterns Emergent biological functions from complex interactions Foraging Patterns in complex systems Plant development Scaling laws of complex systems

来源：评论

学校读者我要写书评

暂无评论

Having Hope in Hops: New Spanners, Preservers and Lower Bounds for Hopsets

Having Hope in Hops: New Spanners, Preservers and Lower Boun...

引用

Annual IEEE Symposium on Foundations of computer science

作者： Shimon Kogan Merav Parter Department of Computer Science and Applied Math Weizmann Institute Rehovot Israel

ISBN: (数字)9781665455190

ISBN: (纸本)9781665455206

Hopsets and spanners are fundamental graph structures, playing a key role in shortest path computation, distributed communication, and more. A (near-exact) hopset for a given graph G is a (small) subset of weighted edges H that when added to the graph G reduces the number of hops (edges) of near-exact shortest paths. Spanners and distance preservers, on the other hand, ask for removing many edges from the graph while approximately preserving shortest path *** provide a general reduction scheme from graph hopsets to the known metric compression schemes of spanners, emulators and distance preservers. Consequently, we get new and improved upper bound constructions for the latter, as well as, new lower bound results for hopsets. Our main results include:•For n-vertex directed weighted graphs, one can provide $(1+\epsilon)$-approximate distance preservers 1 for p pairs in $V\times V$ with $O_{\epsilon}(n\cdot p^{2/5}+(np)^{2/3})$ edges. For $p\geq n^{5/4}$, this matches the state-of-the art bounds for reachability preservers by [Abboud and Bodwin, SODA 2018] and the lower bound for exact-distance preservers by [Bodwin, SODA 2016].•For n-vertex undirected weighted graphs, one can provide $(1+\epsilon)$ distance preserves with $\overline{O}_{\epsilon}(n^{1+o(1)}+p\cdot n^{o(1)})$ edges. So far, such bounds could be obtained only for unweighted graphs. Consequently, we also get improved sourcewise spanners [Roditty, Thorup and Zwick, ICALP 2005] and spanners with slack [Chan, Dinitz and Gupta, ESA 2006].•Exact hopsets of linear size admit a worst-case hopbound of $\beta=\Omega(n^{1/3})$. This holds even for undirected weighted graphs, improving upon the $\Omega(n^{1/6})$ lower bound by [Huang and Pettie, SIAM J. Discret. math.2021]. Interestingly this matches the recent diameter bound achieved for linear directed shortcuts. 1 I.e., subgraphs that preserve the pairwise distances up to a multiplicative stretch of (1+$\epsilon$).More conceptually, our work makes a si

关键词： Measurement computer science Upper bound Art

来源：评论

学校读者我要写书评

暂无评论

BUZZ: Beehive-structured Sparse KV Cache with Segmented Heavy Hitters for Efficient LLM Inference

arXiv

引用

arXiv 2024年

作者： Zhao, Junqi Fang, Zhijin Li, Shu Yang, Shaohui He, Shichao Department of Computer Science New York University New York United States Department of Statistics and Data Science University of California Los Angeles United States Department of Mathematical Science Beihang University Beijing China School of Computer Science University of Leed Leeds United Kingdom Department of Computer Science and Applied Math Brandeis University Boston United States

Large language models (LLMs) are essential in natural language processing but often struggle with inference speed and computational efficiency, limiting real-time deployment. The key-value (KV) cache mechanism reduces computational overhead in transformer models, but challenges in maintaining contextual understanding remain. In this paper, we propose BUZZ, a novel KV caching algorithm that leverages structured contextual information to minimize cache memory usage while enhancing inference speed. BUZZ employs a beehive-structured sparse cache, incorporating a sliding window to capture recent information and dynamically segmenting historical tokens into chunks to prioritize important tokens in local neighborhoods. We evaluate BUZZ on four real-world datasets: CNN/Daily Mail, XSUM, Wikitext, and 10-QA. Our results demonstrate that BUZZ (1) reduces cache memory usage by 2.5× in LLM inference while maintaining over 99% accuracy in long-text summarization, and (2) surpasses state-of-the-art performance in multi-document question answering by 7.69% under the same memory limit, where full cache methods encounter out-of-memory issues. Additionally, BUZZ achieves significant inference speedup with a log n time complexity. The code is available at: https://***/JunqiZhao888/buzz-llm. Copyright © 2024, The Authors. All rights reserved.

关键词： Cache memory

来源：评论

学校读者我要写书评

暂无评论

Expansion of High-Dimensional Cubical Complexes: with Application to Quantum Locally Testable Codes

Expansion of High-Dimensional Cubical Complexes: with Applic...

引用

Annual IEEE Symposium on Foundations of computer science

作者： Irit Dinur Ting-Chun Lin Thomas Vidick Department of Applied Math and Computer Science The Weizmann Institute of Science Rehovot Israel Department of Physics University of California at San Diego San Diego USA Hon Hai Research Institute Taipei Taiwan

ISBN: (数字)9798331516741

ISBN: (纸本)9798331516758

We introduce a high-dimensional cubical complex, for any dimension $t \in \math.b{N}$ , and apply it to the design of quantum locally testable codes. Our complex is a natural generalization of the constructions by Panteleev and Kalachev and by Dinur et. al of a square complex (case $t=2$ ), which have been applied to the design of classical locally testable codes (LTC) and quantum low-density parity check codes (qLDPC) respectively. We turn the geometric (cubical) complex into a chain complex by relying on constant-sized local codes $h_applied, \ldots,h_{t}$ as gadgets. A recent result of Panteleev and Kalachev on existence of tuples of codes that are product expanding enables us to prove lower bounds on the cycle and co-cycle expansion of our chain complex. For $t=4$ our construction gives a new family of “almost-good” quantum LTCs - with constant relative rate, inverse-polylogarithmic relative distance and soundness, and constant-size parity checks. Both the distance of the quantum code and its local testability are proven directly from the cycle and co-cycle expansion of our chain complex.

关键词： computer science Parity check codes

来源：评论

学校读者我要写书评

暂无评论

Deep Learning-based Sentiment Classification: A Comparative Survey

arXiv

引用

arXiv 2023年

作者： Kayed, Mohamed Díaz Redondo, Rebeca P. Mabrouk, Alhassan Computer Science Department Faculty of Computers and Artificial Intelligence Beni-Suef University Egypt Information & Computing Lab AtlanTTIC Research Center Telecommunication Engineering School Universidade de Vigo Spain Math. and Computer Science Department Faculty of Science Beni-Suef University Egypt

Recently, Deep Learning (DL) approaches have been applied to solve the Sentiment Classification (SC) problem, which is a core task in reviews mining or Sentiment Analysis (SA). The performances of these approaches are affected by different factors. This paper addresses these factors and classifies them into three categories: data preparation based factors, feature representation based factors and the classification techniques based factors. The paper is a comprehensive literature-based survey that compares the performance of more than 100 DL-based SC approaches by using 21 public datasets of reviews given by customers within three specific application domains (products, movies and restaurants). These 21 datasets have different characteristics (balanced/imbalanced, size, etc.) to give a global vision for our study. The comparison explains how the proposed factors quantitatively affect the performance of the studied DL-based SC approaches. Copyright © 2023, The Authors. All rights reserved.

关键词： Sentiment analysis

来源：评论

学校读者我要写书评

暂无评论

Numerical and analytical calculations of orbit-wise synthetic spectra from two-step gamma-ray fusion reactions 50

Numerical and analytical calculations of orbit-wise syntheti...

引用

50th EPS Conference on Plasma Physics, EPS 2024

作者： Valentini, A. Nocente, M. Eriksson, J. Järleblad, H. Moseev, D. Reman, B.C.G. Rud, M. Snicker, A. Stagner, L. Salewski, M. Department of Physics Technical University of Denmark Kgs Lyngby2800 Denmark Department of Physics University of Milano-Bicocca Milan20126 Italy Department of Physics and Astronomy Uppsala University Uppsala75120 Sweden Department of Appl. Math. & Computer Science Technical University of Denmark Kgs Lyngby2800 Denmark Max-Planck-Institut fur Plasmaphysik Wendelsteinstr. 1 Greifswald17491 Germany Laboratory for Plasma Physics LPP-ERM/KMS BrusselsB-1000 Belgium Department of Applied Physics Aalto University AaltoFI-00076 Finland General Atomics P.O. Box 85608 San DiegoCA92186-5609 United States

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：