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

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

来源：评论

学校读者我要写书评

暂无评论

The Grad of a Graph and Classes with Bounded Expansion

引用

Electronic Notes in Discrete mathematics 2005年 22卷 101-106页

作者： Nešetřil, Jaroslav Ossona de Mendez, Patrice Department of Applied Mathematics Institute of Theoretical Computer Science Charles University Praha Czech Republic Centre d'Analyse Mathématiques Sociales - CNRS UMR 8557 Paris France

We introduce classes of graphs with bounded expansion as a generalization of both proper minor closed classes and degree bounded classes. Such classes are based on a new invariant, the greatest reduced average density (grad) of G with rank r, ∇_r (G). We generalize to these classes some results proved for proper minor closed classes and bounded degree graphs, such as the existence of low tree-width colorings and homomorphism dualities. © 2005 Elsevier B.V. All rights reserved.

关键词： Bounded expansion Coloring Constrained orientation Homomorphism Restricted duality Transitive fraternal augmentation Tree-depth

来源：评论

学校读者我要写书评

暂无评论

Fraternal Augmentations of graphs, Coloration and Minors

引用

Electronic Notes in Discrete mathematics 2007年 28卷 223-230页

We introduce classes of graphs with bounded expansion as a generalization of both proper minor closed classes and degree bounded classes. Such classes are based on a new invariant, the greatest reduced average density (grad) of G with rank r, ∇_r (G). We generalize to these classes some results proved for proper minor closed classes and bounded degree graphs, such as the existence of low tree-width colorings, a linear time algorithm to check subgraph isomorphism for a fixed pattern and homomorphism dualities. © 2007 Elsevier B.V. All rights reserved.

关键词： Bounded expansion Coloring Graph Algorithm Homomorphism Ramsey number Restricted duality Subgraph Isomorphism Transitive fraternal augmentation Tree-depth

来源：评论

学校读者我要写书评

暂无评论

Grassroots Systems: Concept, Examples, Implementation and Applications

arXiv

引用

arXiv 2023年

作者： Shapiro, Ehud Department of Computer Science and Applied Math Weizmann Institute of Science Israel

Informally, a grassroots system is a distributed system that can have multiple instances, independent of each other and of any global resources, that can interoperate once interconnected. More formally, in a grassroots system the set of all correct behaviors of a set of agents P is strictly included in the set of the correct behaviors of P when embedded within a larger set of agents P′ ⊃ P: Included, meaning that members of P are correct to ignore outside agents indefinitely;strictly included, meaning that the interaction of members of P with outside agents is also a possible and correct behavior. Client-server/cloud computing systems are not grassroots, and neither are systems designed to have a single global instance (Bitcoin/Ethereum with hardwired seed miners/bootnodes), and systems that rely on a single global data structure (IPFS, DHTs). An example grassroots system would be a serverless smartphone-based social network supporting multiple independently-budding communities that can merge when a member of one community becomes also a member of another. Grassroots applications are potentially important as they may allow people to conduct their social, economic, civic, and political lives in the digital realm solely using the networked computing devices they own and operate (e.g., smartphones), free of third-party control, surveillance, manipulation, coercion, or rent seeking (e.g., by global digital platforms such as Facebook or Bitcoin). Here, we formalize the notion of grassroots systems and grassroots implementations;specify an abstract grassroots dissemination protocol;describe and prove an implementation of grassroots dissemination for the model of asynchrony;extend the implementation to mobile (address-changing) devices that communicate via an unreliable network (e.g. smartphones using UDP);and discuss how grassroots dissemination can realize applications that support digital sovereignty – grassroots social networking and grassroots currencies. The mathemat

关键词： Smartphones

来源：评论

学校读者我要写书评

暂无评论

New construction of ensemble classifiers for imbalanced datasets

New construction of ensemble classifiers for imbalanced data...

引用

2010 IEEE International Conference on Intelligent Systems and Knowledge Engineering, ISKE 2010

作者： Zhai, Yun Yang, Bingru Ma, Nan Ruan, Da School of Information Engineering University of Science and Technology Beijing Beijing China College of Computer Science Liaocheng University Liaocheng China College of Information Beijing Union University Beijing China Department of Applied Math and Computer Science Ghent University Krijgslaan Belgium

ISBN: (纸本)9781424467907

Learning in the presence of data imbalances presents a great challenge to machine learning. Imbalanced data sets represent a significant problem because the corresponding classifier has a tendency to ignore samples which have smaller representation in the training sets. In this paper, we propose an ensemble-based learning algorithm as a new ensemble classifier model called as SVM-C5.0 Ensemble Classifier Model, SCECM. SCECM adopts a differentiated sampling rate algorithm (DSRA) based on an improved Adaboost algorithm and further employs unique classifier-selection strategy, novel classifier integration approach and original classification decision-making method. Comparative experimental results show that the proposed approach improves performance for the minority class while preserving the ability to recognize examples from the majority classes. © 2010 IEEE.

关键词： Data mining

来源：评论

学校读者我要写书评

暂无评论

A novel robust adaptive fuzzy controller

A novel robust adaptive fuzzy controller

引用

Proceedings of the 4th World Congress on Intelligent Control and Automation

作者： Liu, Xiaohua Wang, Xiuhong Fen, Enmin Dept. of Math. and Computer Science Yantai Normal University Yantai 264025 China Department of Applied Mathematics Dalian University of Technology Dalian 112064 China

ISBN: (纸本)0780372689

For a class of continuous - time nonlinear system, a novel robust adaptive fuzzy controller is proposed by using of Lyapunov method. It is proven that the control algorithm is globally stable, the output tracking - error of the system can convergence to a domain of zero under the assumptions. As a result, the system controled has stronger robustness for disturbance and modeling error.

关键词： Fuzzy control

来源：评论

学校读者我要写书评

暂无评论

Direct estimation of information divergence using nearest neighbor ratios

Direct estimation of information divergence using nearest ne...

引用

2017 IEEE International Symposium on Information Theory, ISIT 2017

作者： Noshad, Morteza Moon, Kevin R. Sekeh, Salimeh Yasaei Hero, Alfred O. University of Michigan Electrical Engineering and Computer Science Ann ArborMI United States Yale University Genetics and Applied Math Department New HavenCT United States

ISBN: (纸本)9781509040964

We propose a direct estimation method for Rényi and f-divergence measures based on a new graph theoretical interpretation. Suppose that we are given two sample sets X and Y, respectively with N and M samples, where η := M/N is a constant value. Considering the k-nearest neighbor (k-NN) graph of Y in the joint data set (X, Y), we show that the average powered ratio of the number of X points to the number of Y points among all k-NN points is proportional to Rényi divergence of X and Y densities. A similar method can also be used to estimate f-divergence measures. We derive bias and variance rates, and show that for the class of γ-Hölder smooth functions, the estimator achieves the MSE rate of O(N-2γ/(γ+d)). Furthermore, by using a weighted ensemble estimation technique, for density functions with continuous and bounded derivatives of up to the order d, and some extra conditions at the support set boundary, we derive an ensemble estimator that achieves the parametric MSE rate of O(1/N). Our estimator requires no boundary correction, and remarkably, the boundary issues do not show up. Our approach is also more computationally tractable than other competing estimators, which makes them appealing in many practical applications. © 2017 IEEE.

关键词： Nearest neighbor search

来源：评论

学校读者我要写书评

暂无评论

Space-time behavior based correlation

Space-time behavior based correlation

引用

Conference on computer Vision and Pattern Recognition (CVPR)

作者： E. Shechtman M. Irani Department of Computer Science and Applied Math Weizmann Institute of Science Rehovot Israel

We introduce a behavior-based similarity measure which tells us whether two different space-time intensity patterns of two different video segments could have resulted from a similar underlying motion field. This is done directly from the intensity information, without explicitly computing the underlying motions. Such a measure allows us to detect similarity between video segments of differently dressed people performing the same type of activity. It requires no foreground/background segmentation, no prior learning of activities, and no motion estimation or tracking. Using this behavior-based similarity measure, we extend the notion of 2-dimensional image correlation into the 3-dimensional space-time volume, thus allowing to correlate dynamic behaviors and actions. Small space-time video segments (small video clips) are "correlated" against entire video sequences in all three dimensions (x,y, and t). Peak correlation values correspond to video locations with similar dynamic behaviors. Our approach can detect very complex behaviors in video sequences (e.g., ballet movements, pool dives, running water), even when multiple complex activities occur simultaneously within the field-of-view of the camera.

关键词： Motion estimation Video sequences Motion measurement Image segmentation Videoconference Performance evaluation Tracking Volume measurement Optical filters Apertures

来源：评论

学校读者我要写书评

暂无评论

Matching Local Self-Similarities across Images and Videos

Matching Local Self-Similarities across Images and Videos

引用

Conference on computer Vision and Pattern Recognition (CVPR)

作者： Eli Shechtman Michal Irani Department of Computer Science and Applied Math Weizmann Institute of Science Rehovot Israel

We present an approach for measuring similarity between visual entities (images or videos) based on matching internal self-similarities. What is correlated across images (or across video sequences) is the internal layout of local self-similarities (up to some distortions), even though the patterns generating those local self-similarities are quite different in each of the images/videos. These internal self-similarities are efficiently captured by a compact local "self-similarity descriptor"', measured densely throughout the image/video, at multiple scales, while accounting for local and global geometric distortions. This gives rise to matching capabilities of complex visual data, including detection of objects in real cluttered images using only rough hand-sketches, handling textured objects with no clear boundaries, and detecting complex actions in cluttered video data with no prior learning. We compare our measure to commonly used image-based and video-based similarity measures, and demonstrate its applicability to object detection, retrieval, and action detection.

关键词： Object detection Pixel Image edge detection Distortion measurement Video sequences Image retrieval Filters Heart Image recognition computer science

来源：评论

学校读者我要写书评

暂无评论

A New Interactive Hashing Theorem

A New Interactive Hashing Theorem

引用

Annual IEEE Conference on Computational Complexity

作者： Iftach Haitner Omer Reingold Department of Computer Science and Applied Math Weizmann Institute of Science Rehovot Israel

Interactive hashing, introduced by Naor, Ostrovsky, Venkatesan and Yung (CRYPTO '92), plays an important role in many cryptographic protocols. In particular, it is a major component in all known constructions of statistically- hiding commitment schemes and of zero-knowledge arguments based on general one-way permutations and on one- way functions. Interactive hashing with respect to a one-way permutation f, is a two-party protocol that enables a sender that knows y = f(x) to transfer a random hash z = h(y) to a receiver. The receiver is guaranteed that the sender is committed to y (in the sense that it cannot come up with x and x' such that f(x) Dagger f(x') but h(f(x)) = h(f(x')) = z). The sender is guaranteed that the receiver does not learn any additional information on y. In particular, when h is a two-to-one hash function, the receiver does not learn which of the two pre images {y,y'} = h -1 (z) is the one the sender can invert with respect to f. This paper reexamines the notion of interactive hashing. We give an alternative proof for the Naor et. al. protocol, which seems to us significantly simpler and more intuitive than the original one. Moreover, the new proof achieves much better parameters (in terms of how security preserving the reduction is). Finally, our proof implies a more versatile interactive hashing theorem for a more general setting than that of the Naor et. al. protocol. One generalization relates to the selection of hash function h (allowing much more flexibility). More importantly, the theorem applies to the case where the underlying function f is hard- to-invert only on some given (possibly sparse) subset of the output strings. In other words, the theorem is tuned towards hashing of a value y that may be distributed over a sparse subset of the domain (rather than uniform on the entire domain as a random output of a one-way permutation is). Our interest in interactive hashing is in part as a very appealing object (i.e., independent of any pa

关键词： computer science Cryptographic protocols Cryptography Information security

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：