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

An infrastructure software perspective toward computation offloading between executable specifications and foundation models

引用

science China(Information sciences) 2025年第4期68卷 380-382页

作者： Dezhi RAN Mengzhou WU Yuan CAO Assaf MARRON David HAREL Tao XIE Key Laboratory of High Confidence Software Technologies (PKU) Ministry of Education School of Computer SciencePeking University School of Electronics Engineering and Computer Science Peking University Department of Computer Science and Applied Mathematics Weizmann Institute of Science

Foundation models(FMs) [1] have revolutionized software development and become the core components of large software systems. This paradigm shift, however, demands fundamental re-imagining of software engineering theories and methodologies [2]. Instead of replacing existing software modules implemented by symbolic logic, incorporating FMs' capabilities to build software systems requires entirely new modules that leverage the unique capabilities of ***, while FMs excel at handling uncertainty, recognizing patterns, and processing unstructured data, we need new engineering theories that support the paradigm shift from explicitly programming and maintaining user-defined symbolic logic to creating rich, expressive requirements that FMs can accurately perceive and implement.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Consensus Learning with Deep Sets for Essential Matrix Estimation 38

Consensus Learning with Deep Sets for Essential Matrix Estim...

引用

38th Conference on Neural Information Processing Systems, NeurIPS 2024

作者： Moran, Dror Margalit, Yuval Trostianetsky, Guy Khatib, Fadi Galun, Meirav Basri, Ronen Department of Computer Science and Applied Mathematics Weizmann Institute of Science Israel

Robust estimation of the essential matrix, which encodes the relative position and orientation of two cameras, is a fundamental step in structure from motion pipelines. Recent deep-based methods achieved accurate estimation by using complex network architectures that involve graphs, attention layers, and hard pruning steps. Here, we propose a simpler network architecture based on Deep Sets. Given a collection of point matches extracted from two images, our method identifies outlier point matches and models the displacement noise in inlier matches. A weighted DLT module uses these predictions to regress the essential matrix. Our network achieves accurate recovery that is superior to existing networks with significantly more complex architectures. © 2024 Neural information processing systems foundation. All rights reserved.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Distributed Maximum Flow in Planar Graphs 38

Brief Announcement: Distributed Maximum Flow in Planar Graph...

引用

38th International Symposium on Distributed Computing, DISC 2024

作者： Abd-Elhaleem, Yaseen Dory, Michal Parter, Merav Weimann, Oren Department of Computer Science University of Haifa Israel Department of Computer Science and Applied Mathematics Weizmann Institute of Science Rehovot Israel

ISBN: (纸本)9783959773522

The dual of a planar graph G is a planar graph G∗ that has a vertex for each face of G and an edge for each pair of adjacent faces of G. The profound relationship between a planar graph and its dual has been the algorithmic basis for solving numerous (centralized) classical problems on planar graphs involving distances, flows, and cuts. In the distributed setting however, the only use of planar duality is for finding a recursive decomposition of G [DISC 2017, STOC 2019]. In this paper, we extend the distributed algorithmic toolkit (such as recursive decompositions and minor-aggregations) to work on the dual graph G∗. These tools can then facilitate various algorithms on G by solving a suitable dual problem on G∗. Given a directed planar graph G with hop-diameter D, our key result is an Õ(D2)-round algorithm1 for Single Source Shortest Paths on G∗, which then implies an Õ(D2)-round algorithm for Maximum st-Flow on G. Prior to our work, no Õ(Poly(D))-round algorithm was known for Maximum st-Flow. We further obtain a D·no(1)-rounds (1 + ϵ)-approximation algorithm for Maximum st-Flow on G when G is undirected and s and t lie on the same face. Finally, we give a near optimal Õ(D)-round algorithm for computing the weighted girth of G. The main challenges in our work are that G∗ is not the communication graph (e.g., a vertex of G is mapped to multiple vertices of G∗), and that the diameter of G∗ can be much larger than D (i.e., possibly by a linear factor). We overcome these challenges by carefully defining and maintaining subgraphs of the dual graph G∗ while applying the recursive decomposition on the primal graph G. The main technical difficulty, is that along the recursive decomposition, a face of G gets shattered into (disconnected) components yet we still need to treat it as a dual node. © Yaseen Abd-Elhaleem, Michal Dory, Merav Parter, and Oren Weimann.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

From Donkeys to Kings in Tournaments 32

From Donkeys to Kings in Tournaments

引用

32nd Annual European Symposium on Algorithms, ESA 2024

作者： Abboud, Amir Grossman, Tomer Naor, Moni Solomon, Tomer Department of Computer Science and Applied Mathematics Weizmann Institute of Science Rehovot Israel Tel Aviv University Israel

ISBN: (纸本)9783959773386

A tournament is an orientation of a complete graph. A vertex that can reach every other vertex within two steps is called a king. We study the complexity of finding k kings in a tournament graph. We show that the randomized query complexity of finding k ≤ 3 kings is O(n), and for the deterministic case it takes the same amount of queries (up to a constant) as finding a single king (the best known deterministic algorithm makes O(n3/2) queries). On the other hand, we show that finding k ≥ 4 kings requires Ω(n2) queries, even in the randomized case. We consider the RAM model for k ≥ 4. We show an algorithm that finds k kings in time O(kn2), which is optimal for constant values of k. Alternatively, one can also find k ≥ 4 kings in time nω (the time for matrix multiplication). We provide evidence that this is optimal for large k by suggesting a fine-grained reduction from a variant of the triangle detection problem. © Amir Abboud, Tomer Grossman, Moni Naor, and Tomer Solomon;licensed under Creative Commons License CC-BY 4.0.

关键词： Graph theory

来源：评论

学校读者我要写书评

暂无评论

On the Effectiveness of ViT Features as Local Semantic Descriptors 17th

On the Effectiveness of ViT Features as Local Semantic De...

引用

17th European Conference on computer Vision, ECCV 2022

作者： Amir, Shir Gandelsman, Yossi Bagon, Shai Dekel, Tali Department of Computer Science and Applied Mathematics The Weizmann Institute of Science Rehovot Israel Berkeley United States

ISBN: (纸本)9783031250682

We study the use of deep features extracted from a pre-trained Vision Transformer (ViT) as dense visual descriptors. We observe and empirically demonstrate that such features, when extracted from a self-supervised ViT model (DINO-ViT), exhibit several striking properties, including: (i) the features encode powerful, well-localized semantic information, at high spatial granularity, such as object parts;(ii) the encoded semantic information is shared across related, yet different object categories, and (iii) positional bias changes gradually throughout the layers. These properties allow us to design simple methods for a variety of applications, including co-segmentation, part co-segmentation and semantic correspondences. To distill the power of ViT features from convoluted design choices, we restrict ourselves to lightweight zero-shot methodologies (e.g., binning and clustering) applied directly to the features. Since our methods require no additional training nor data, they are readily applicable across a variety of domains. We show by extensive qualitative and quantitative evaluation that our simple methodologies achieve competitive results with recent state-of-the-art supervised methods, and outperform previous unsupervised methods by a large margin. Code is available in https://***/. © 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.

关键词： Zero-shot learning

来源：评论

学校读者我要写书评

暂无评论

High-Dynamic Range ADC for Finite-Rate-of-Innovation Signals 48

High-Dynamic Range ADC for Finite-Rate-of-Innovation Signals

引用

48th IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2023

作者： Mulleti, Satish Eldar, Yonina C. Bombay Department of Electrical Engineering India Weizmann Institute of Science Faculty of Math and Computer Science Israel

ISBN: (纸本)9781728163277

Modulo folding can be used to sample high-dynamic range signals without increasing the dynamic range of the sampler. Specifically, folding is used prior to sampling and then the folded signal is sampled. After sampling, unfolding algorithms are used to compute the true samples (up to a constant factor) from the folded ones. In this work, we consider a modulo sampling framework for finite rate of innovation (FRI) signals which are used to model signals in time of flight imaging. We suggest compactly supported sum-of-sincs filter as a sampling kernel prior to modulo folding and sampling. We derive conditions on the sampling rate and filter coefficients which lead to unfolding of the samples up to an unknown constant. We then propose a modified annihilating filter approach that can uniquely determine the FRI parameters from the unfolded samples with a constant unknown offset. We show that the proposed framework outperforms existing techniques in the presence of noise. © 2023 IEEE.

关键词： Signal sampling

来源：评论

学校读者我要写书评

暂无评论

Fully-Scalable MPC Algorithms for Clustering in High Dimension 51

Fully-Scalable MPC Algorithms for Clustering in High Dimensi...

引用

51st International Colloquium on Automata, Languages, and Programming, ICALP 2024

作者： Czumaj, Artur Gao, Guichen Jiang, Shaofeng H.-C. Krauthgamer, Robert Veselý, Pavel Department of Computer Science University of Warwick Coventry United Kingdom School of Computer Science Peking University Beijing China Department of Computer Science and Applied Mathematics Weizmann Institute of Science Rehovot Israel Computer Science Institute of Charles University Prague Czech Republic

ISBN: (纸本)9783959773225

We design new parallel algorithms for clustering in high-dimensional Euclidean spaces. These algorithms run in the Massively Parallel Computation (MPC) model, and are fully scalable, meaning that the local memory in each machine may be nσ for arbitrarily small fixed σ > 0. Importantly, the local memory may be substantially smaller than the number of clusters k, yet all our algorithms are fast, i.e., run in O(1) rounds. We first devise a fast MPC algorithm for O(1)-approximation of uniform Facility Location. This is the first fully-scalable MPC algorithm that achieves O(1)-approximation for any clustering problem in general geometric setting;previous algorithms only provide poly(log n)-approximation or apply to restricted inputs, like low dimension or small number of clusters k;e.g. [Bhaskara and Wijewardena, ICML’18;Cohen-Addad et al., NeurIPS’21;Cohen-Addad et al., ICML’22]. We then build on this Facility Location result and devise a fast MPC algorithm that achieves O(1)-bicriteria approximation for k-Median and for k-Means, namely, it computes (1 + Ε)k clusters of cost within O(1/Ε2)-factor of the optimum for k clusters. A primary technical tool that we introduce, and may be of independent interest, is a new MPC primitive for geometric aggregation, namely, computing for every data point a statistic of its approximate neighborhood, for statistics like range counting and nearest-neighbor search. Our implementation of this primitive works in high dimension, and is based on consistent hashing (aka sparse partition), a technique that was recently used for streaming algorithms [Czumaj et al., FOCS’22]. © Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Pavel Veselý.

关键词： Nearest neighbor search

来源：评论

学校读者我要写书评

暂无评论

Drop the GAN: In Defense of Patches Nearest Neighbors as Single Image Generative Models

Drop the GAN: In Defense of Patches Nearest Neighbors as Sin...

引用

2022 IEEE/CVF Conference on computer Vision and Pattern Recognition, CVPR 2022

作者： Granot, Niv Feinstein, Ben Shocher, Assaf Bagon, Shai Irani, Michal The Weizmann Institute of Science Dept. of Computer Science and Applied Math Israel Israel

ISBN: (数字)9781665469463

ISBN: (纸本)9781665469463

Image manipulation dates back long before the deep learning era. The classical prevailing approaches were based on maximizing patch similarity between the input and generated output. Recently, single-image GANs were introduced as a superior and more sophisticated solution to image manipulation tasks. Moreover, they offered the opportunity not only to manipulate a given image, but also to generate a large and diverse set of different outputs from a single natural image. This gave rise to new tasks, which are considered 'GAN-only'. However, despite their impressiveness, single-image GANs require long training time (usually hours) for each image and each task and often suffer from visual artifacts. In this paper we revisit the classical patch-based methods, and show that - unlike previously believed - classical methods can be adapted to tackle these novel 'GAN-only' tasks. Moreover, they do so better and faster than single-image GAN-based methods. More specifically, we show that: (i) by introducing slight modifications, classical patch-based methods are able to unconditionally generate diverse images based on a single natural image;(ii) the generated output visual quality exceeds that of single-image GANs by a large margin (confirmed both quantitatively and qualitatively);(iii) they are orders of magnitude faster (runtime reduced from hours to seconds). 22This project received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 788535), and the Carolito Stiftung. Dr Bagon is a Robin Chemers Neustein AI Fellow. © 2022 IEEE.

关键词： Training Deep learning Visualization Technological innovation computer vision Runtime Europe

来源：评论

学校读者我要写书评

暂无评论

An algorithm with optimal dimension-dependence for zero-order nonsmooth nonconvex stochastic optimization

The Journal of Machine Learning Research

引用

The Journal of Machine Learning Research 2024年第1期25卷 5918-5931页

作者： Guy Kornowski Ohad Shamir Department of Computer Science and Applied Mathematics Weizmann Institute of Science Rehovot Israel

We study the complexity of producing (δ, ε)-stationary points of Lipschitz objectives which are possibly neither smooth nor convex, using only noisy function evaluations. Recent works proposed several stochastic zero-order algorithms that solve this task, all of which suffer from a dimension-dependence of Ω(d3/2) where d is the dimension of the problem, which was conjectured to be optimal. We refute this conjecture by providing a faster algorithm that has complexity O(dδ-1ε-3), which is optimal (up to numerical constants) with respect to d and also optimal with respect to the accuracy parameters δ, ε, thus solving an open question due to Lin et al. (2022). Moreover, the convergence rate achieved by our algorithm is also optimal for smooth objectives, proving that in the nonconvex stochastic zero-order setting, nonsmooth optimization is as easy as smooth optimization. We provide algorithms that achieve the aforementioned convergence rate in expectation as well as with high probability. Our analysis is based on a simple yet powerful lemma regarding the Goldstein-subdifferential set, which allows utilizing recent advancements in first-order nonsmooth nonconvex optimization.

关键词： nonsmooth nonconvex optimization stochastic optimization zero-order gradient-free Goldstein subdifferential

来源：评论

学校读者我要写书评

暂无评论

Adjacency Sketches in Adversarial Environments

arXiv

引用

arXiv 2023年

作者： Naor, Moni Pekel, Eugene Department of Computer Science and Applied Math Weizmann Institute of Science

An adjacency sketching or implicit labeling scheme for a family F of graphs is a method that defines for any n vertex G ∈ F an assignment of labels to each vertex in G, so that the labels of two vertices tell you whether or not they are adjacent. The goal is to come up with labeling schemes that use as few bits as possible to represent the labels. By using randomness when assigning labels, it is sometimes possible to produce adjacency sketches with much smaller label sizes, but this comes at the cost of introducing some probability of error. Both deterministic and randomized labeling schemes have been extensively studied, as they have applications for distributed data structures and deeper connections to universal graphs and communication complexity. The main question of interest is which graph families have schemes using short labels, usually O(log n) in the deterministic case or constant for randomized sketches. In this work we consider the resilience of probabilistic adjacency sketches against an adversary making adaptive queries to the labels. This differs from the previously analyzed probabilistic setting which is "one shot". We show that in the adaptive adversarial case the size of the labels is tightly related to the maximal degree of the graphs in F . This results in a stronger characterization compared to what is known in the non-adversarial setting. In more detail, we construct sketches that fail with probability Ε for graphs with maximal degree d using 2d log(1/Ε) bit labels and show that this is roughly the best that can be done for any specific graph of maximal degree d, e.g. a d-ary *** Codes 68W20, 68W40, 68Q87 Copyright © 2023, The Authors. All rights reserved.

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：