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

Sublinear Computation Paradigm: constant-time algorithms and Sublinear Progressive algorithms

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2022年第3期E105A卷 131-141页

作者： Chiba, Kyohei Ito, Hiro Univ Electrocommun Sch Informat & Engn Chofu Tokyo 1828585 Japan

The challenges posed by big data in the 21st Century are complex: Under the previous common sense, we considered that polynomial-time algorithms are practical;however, when we handle big data, even a linear-time algorithm may be too slow. Thus, sublinear- and constant-time algorithms are required. The academic research project, "Foundations of Innovative algorithms for Big Data," which was started in 2014 and will finish in September 2021, aimed at developing various techniques and frameworks to design algorithms for big data. In this project, we introduce a "Sublinear Computation Paradigm." Toward this purpose, we first provide a survey of constant-time algorithms, which are the most investigated framework of this area, and then present our recent results on sublinear progressive algorithms. A sublinear progressive algorithm first outputs a temporary approximate solution in constant time, and then suggests better solutions gradually in sublinear-time, finally finds the exact solution. We present Sublinear Progressive Algorithm Theory (SPA Theory, for short), which enables to make a sublinear progressive algorithm for any property if it has a constant-time algorithm and an exact algorithm (an exponential-time one is allowed) without losing any computation time in the big-O sense.

关键词： sublinear computation paradigm big data sublinear-time algorithms constant-time algorithms tester progressive algorithms

来源：评论

学校读者我要写书评

暂无评论

PARALLEL constant-time CONNECTIVITY algorithms ON A RECONFIGURABLE NETWORK OF PROCESSORS

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1995年第1期6卷 105-110页

作者： ALNUWEIRI, HM Department of Electrical Engineering University of British Columbia Vancouver BC Canada

This short note presents constant-time algorithms for labeling the connected components of an image on a network of processors with a wide reconfigurable bus. The algorithms are based on a processor indexing scheme which employs constant-weight codes. The use of such codes enables identifying a single representative processor for each component in a constant number of steps. The proposed algorithms can label an N x N image in O(1) time using N-2 processors, which is optimal. Furthermore, the proposed techniques lead to an O(log N/log log N)- time image labeling algorithm on a network of N-2 processors with a reconfigurable bus of width log N bits. It is shown that these techniques can be applied to labeling an undirected N-vertex graph represented by an adjacency matrix.

关键词： RECONFIGURABLE NETWORKS OF PROCESSORS PARALLEL PROCESSING constant-time algorithms constant-WEIGHT CODES LABELING CONNECTED COMPONENTS IMAGE COMPUTATIONS GRAPHS ARRAY PROCESSING

来源：评论

学校读者我要写书评

暂无评论

Streamlining CSIDH: Cost-Effective Strategies for Group Actions Evaluation 27th

Streamlining CSIDH: Cost-Effective Strategies for Group Acti...

引用

27th International Conference on Information Security

作者： Zawia, Ahmed Hasan, M. Anwar Univ Waterloo Waterloo ON Canada

ISBN: (纸本)9783031757631;9783031757648

In the realm of post-quantum cryptography, the Commutative Supersingular Isogeny Diffie-Hellman (CSIDH) has drawn considerable attention since its proposal at Asiacrypt 2018. This paper introduces a new batching strategy for computing multiple group actions in CSIDH, which is essential for constructing cryptographic schemes such as zero-knowledge proofs and signature schemes. Two variants of the batching strategy are presented in this work, suited to different security requirements and application contexts. In the first scenario, we focus on situations where group actions are public, aiming to reduce CSIDH's computational cost. Using our strategy, we show that computational costs can be significantly reduced, making it a viable option for schemes in which efficiency is critical. This variant reduces the computational requirements of group actions by roughly up to 14% when compared to non-batched action evaluation. The second variant is towards constant-time group actions, and it reduces computational costs while maintaining resilience to side-channel timing attacks. This article also introduces a new constant-time implementation of CSIDH that, when combined with the second variant, reduces the computation costs of secret action sets by roughly up to 8% compared to individual computation using state-of-the-art constant-time algorithms, while the new constant time alone reduces computation by approximately up to 4%.

关键词： Post-quantum cryptography Isogeny-based cryptography CSIDH constant-time algorithms Digital signatures Zero-knowledge proofs

来源：评论

学校读者我要写书评

暂无评论

A Comprehensive Analysis of constant-time Polynomial Inversion for Post-quantum Cryptosystems 20

A Comprehensive Analysis of Constant-time Polynomial Inversi...

引用

17th ACM International Conference on Computing Frontiers (CF)

作者： Barenghi, Alessandro Pelosi, Gerardo Politecn Milan Milan Italy

ISBN: (纸本)9781450379564

Post-quantum cryptosystems have currently seen a surge in interest thanks to the current standardization initiative by the U.S.A. National Institute of Standards and Technology (NIST). A common primitive in post-quantum cryptosystems, in particular in code-based ones, is the computation of the inverse of a binary polynomial in a binary polynomial ring. In this work, we analyze, realize in software, and benchmark a broad spectrum of binary polynomial inversion algorithms, targeting operand sizes which are relevant for the current second round candidates in the NIST standardization process. We evaluate advantages and shortcomings of the different inversion algorithms, including their capability to run in constant-time, thus preventing timing side-channel attacks.

关键词： Post-quantum Cryptosystems Code-based Cryptography constant-time algorithms Timing Side-channel Attacks

来源：评论

学校读者我要写书评

暂无评论

What Graph Properties Are constant-time Testable? Dense Graphs, Sparse Graphs, and Complex Networks

引用

REVIEW OF SOCIONETWORK STRATEGIES 2019年第2期13卷 101-121页

作者： Ito, Hiro Univ Electrocommun Sch Informat & Engn Tokyo 1820021 Japan

In this paper, we survey what graph properties have been found to be constant-time testable at present. How to handle big data is a very important issue in computer science. Developing efficient algorithms for problems on big data is an urgent task. For this purpose, constant-time algorithms are powerful tools, since they run by reading only a constant-sized part of each input. In other words, the running time is invariant regardless of the size of the input. The idea of constant-time algorithms appeared in the 1990s and spread quickly especially in this century. Research on graph algorithms is one of the best studied areas in theoretical computer science. When we study constant-time algorithms on graphs, we have three models that differ in the way that the graphs are represented: the dense-graph model, the bounded-degree model, and the general model. The first one is used to treat properties on dense graphs, and the other two are used to treat properties on sparse graphs. In this paper, we survey one by one what properties have been found to be constant-time testable in each of the three models.

关键词： constant-time algorithms Property testing Graphs Regularity lemma Hyperfinite Universal testers Complex networks

来源：评论

学校读者我要写书评

暂无评论

A characterization of graph properties testable for general planar graphs with one-sided error (It's all about forbidden subgraphs) 60

A characterization of graph properties testable for general ...

引用

60th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Czumaj, Artur Sohler, Christian Univ Warwick DIMAP Warwick England Univ Warwick Dept Comp Sci Warwick England TU Dortmund Dept Comp Sci Dortmund Germany

ISBN: (纸本)9781728149523

The problem of characterizing testable graph properties (properties that can be tested with a number of queries independent of the input size) is a fundamental problem in the area of property testing. While there has been some extensive prior research characterizing testable graph properties in the dense graphs model and we have good understanding of the bounded degree graphs model, no similar characterization has been known for general graphs, with no degree bounds. In this paper we take on this major challenge and consider the problem of characterizing all testable graph properties in general planar graphs. We consider the model in which a general planar graph can be accessed by the random neighbor oracle that allows access to any given vertex and access to a random neighbor of a given vertex. We show that, informally, a graph property P is testable with one-sided error for general planar graphs if and only if testing P can be reduced to testing for a finite family of finite forbidden subgraphs. While our presentation focuses on planar graphs, our approach extends easily to general minor-free graphs. Our analysis of the necessary condition relies on a recent construction of canonical testers in the random neighbor oracle model that is applied here to the one-sided error model for testing in planar graphs. The sufficient condition in the characterization reduces the problem to the task of testing H-freeness in planar graphs, and is the main and most challenging technical contribution of the paper: we show that for planar graphs (with arbitrary degrees), the property of being H-free is testable with one-sided error for every finite graph H, in the random neighbor oracle model.

关键词： property testing H-freeness general planar graphs minor-free graphs constant-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Planar Graphs: Random Walks and Bipartiteness Testing

Planar Graphs: Random Walks and Bipartiteness Testing

引用

52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Czumaj, Artur Monemizadeh, Morteza Onak, Krzysztof Sohler, Christian Univ Warwick Coventry CV4 7AL W Midlands England Goethe Univ Frankfurt Frankfurt Germany CMU Pittsburgh PA 15213 USA TU Dortmund Dortmund Germany

ISBN: (纸本)9780769545714

We initiate the study of the testability of properties in arbitrary planar graphs. We prove that bipartiteness can be tested in constant time. The previous bound for this class of graphs was (O) over tilde(root n), and the constant-time testability was only known for planar graphs with bounded degree. Previously used transformations of unbounded-degree sparse graphs into bounded-degree sparse graphs cannot be used to reduce the problem to the testability of bounded-degree planar graphs. Our approach extends to arbitrary minor-free graphs. Our algorithm is based on random walks. The challenge here is to analyze random walks for a class of graphs that has good separators, i.e., bad expansion. Standard techniques that use a fast convergence to a uniform distribution do not work in this case. Roughly speaking, our analysis technique self-reduces the problem of finding an odd-length cycle in a multigraph G induced by a collection of cycles to another multigraph G' induced by a set of shorter odd-length cycles, in such a way that when a random walks finds a cycle in G' with probability p > 0, then it does so with probability lambda(p) > 0 in G. This reduction is applied until the cycles collapse to self-loops that can be easily detected.

关键词： property testing bipartiteness planar graphs minor-free graphs constant-time algorithms

来源：评论

学校读者我要写书评

暂无评论

A FAST RECONFIGURABLE NETWORK FOR GRAPH CONNECTIVITY AND TRANSITIVE CLOSURE

引用

Parallel Processing Letters 1994年第1N02期4卷 105-115页

作者： HUSSEIN M. ALNUWEIRI Department of Electrical Engineering University of British Columbia Vancouver B.C. V6T 124 Canada

This paper presents a VLSI array for labeling the connected components of a graph on N nodes in O(r) steps using a reconfigurable bus of width m bits, such that and 1≤r≤m. The network architecture consists of an array of simple logic nodes which are connected by a reconfigurable bus. To solve a problem on N nodes, the array uses N processors and N(N−1)/2 switches. The proposed connectivity and transitive closure algorithms are based on a processor indexing scheme which employs constant-weight codes. It is shown that when r is a constant, then the algorithm takes O(1) time using a bus of width O(N 1/r ), and when r=[ log N/ loglog N], the algorithm takes O( log N/ loglog N) time using a bus of width O( log N) bits.

关键词： Parallel processing reconfigurable networks labeling connected components constant-time algorithms graph algorithms constant-weight codes

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：