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

35th Conference on Learning Theory (COLT)

作者： Berg, Tomer Ordentlich, Or Shayevitz, Ofer Tel Aviv Univ Sch Elect Engn Tel Aviv Israel Hebrew Univ Jerusalem Sch Comp Sci & Engn Jerusalem Israel

In this paper we consider the problem of uniformity testing with limited memory. We observe a sequence of independent identically distributed random variables drawn from a distribution p over [n], which is either uniform or is epsilon-far from uniform under the total variation distance, and our goal is to determine the correct hypothesis. At each time point we are allowed to update the state of a finite-memory machine with S states, where each state of the machine is assigned one of the hypotheses, and we are interested in obtaining an asymptotic probability of error at most 0 < delta < 1/2 uniformly under both hypotheses. The main contribution of this paper is deriving upper and lower bounds on the number of states S needed in order to achieve a constant error probability d, as a function of n and e, where our upper bound is O(n log n/epsilon) and our lower bound is Omega(n + 1/epsilon). Prior works in the field have almost exclusively used collision counting for upper bounds, and the Paninski mixture for lower bounds. Somewhat surprisingly, in the limited memory with unlimited samples setup, the optimal solution does not involve counting collisions, and the Paninski prior is not hard. Thus, different proof techniques are needed in order to attain our bounds.

关键词： memory complexity uniformity testing

来源：评论

学校读者我要写书评

暂无评论

A memory complexity Model for Circular Sentences

A Memory Complexity Model for Circular Sentences

引用

2011 2ND International Conference on Innovative Computing and Communication and 2011 Asia-Pacific Conference on Information Technology and Ocean Engineering(CICC-ITOE 2011)

作者： XU Hai yan LinYi University

The memory system has become a key factor to get high performance, especially for those numerical programs. Along with the increasing gap between processors and memories, the traditional calculation complexity analysis is now not sufficient to judge an algorithm or program. The memory complexity also plays an important role. In this paper, a model based on the memory hierarchy technology was proposed to analyze the memory complexity for circular sentences, which are normally the most time-consuming part for numerical programs, and therefore to judge and predict its performance.

关键词： memory complexity Circular sentence memory hierarchy Model

来源：评论

学校读者我要写书评

暂无评论

Improved impossible differential attack on reduced version of Camellia with FL/FL^-1 functions

引用

IET INFORMATION SECURITY 2016年第6期10卷 425-432页

作者： Liu, Ya Yang, Anren Liu, Zhiqiang Li, Wei Wang, Qingju Song, Liang Gu, Dawu Univ Shanghai Sci & Technol Dept Comp Sci & Engn Shanghai 200093 Peoples R China Shanghai Jiao Tong Univ Dept Comp Sci & Engn Shanghai 200240 Peoples R China Donghua Univ Sch Comp Sci & Technol Shanghai 201620 Peoples R China Chinese Acad Sci Inst Informat Engn State Key Lab Informat Secur Beijing 100093 Peoples R China Shanghai Key Lab Integrate Adm Technol Informat S Shanghai 200240 Peoples R China Katholieke Univ Leuven ESAT COSIC B-3001 Leuven Belgium Katholieke Univ Leuven iMinds B-3001 Leuven Belgium

As an ISO/IEC international standard, Camellia has been used in various cryptographic applications. In this study, the authors present the best currently known attacks on Camellia-192/256 with key-dependent layers FL/FL-1 (without the whitening layers) by taking advantage of the intrinsic weakness of keyed functions, the redundancy of key schedule and the early abort technique. Specifically, the authors mount the first impossible differential attack on 13-round Camellia-192 with 2(124.79) chosen plaintexts, 2(186.09) 13-round encryptions and 2(129.79) bytes, while the analysis for the biggest number of rounds in previous results on Camellia-192 worked on 12 rounds. Furthermore, the authors successfully attack on 14-round Camellia-256 with 2(122.14) chosen plaintexts, 2(228.33) 14-round encryptions and 2(134.14) bytes. Compared with the previously best known attack on 14-round Camellia-256, the time and memory complexities are reduced by 2(9.87) times and 2(46.06) times, and the data complexity is comparable.

关键词： ISO standards IEC standards cryptography impossible differential attack Camellia standard ISO international standard IEC international standard cryptographic applications Camellia-192 Camellia-256 time complexity memory complexity data complexity

来源：评论

学校读者我要写书评

暂无评论

On the cost of uniform protocols whose memory consumption is adaptive to interval contention

引用

THEORETICAL COMPUTER SCIENCE 2009年第6-7期410卷 533-545页

作者： Englert, Burkhard Calif State Univ Long Beach Dept Comp Engr & Comp Sci Long Beach CA 90840 USA

Recently, we introduced a novel term, memory-adaptive. whose goal it is to capture what it means for a distributed protocol to most efficiently make use of its shared memory. We proved three results that relate to the memory-adaptive model in the uniform setting. We considered a store/release protocol where processes are required to store a value in shared MWMR memory so that it cannot be overwritten until it has been released by the process. We showed that there do not exist uniformly wait-free store/release protocols using only the basic operations read and write that are memory-adaptive to point contention. We further showed that there exists a uniformly wait-free store/release protocol using only the basic operations read, write, and read-modify-write that is memory-adaptive to interval contention and time-adaptive to total contention. This left a significant gap - it remained open as to whether there exists a uniform, memory adaptive to interval contention store/release protocol that only uses read/write (no read-modify-write) registers. In this paper, we close this gap by showing that no such protocol can exist. We furthermore illustrate the validity and practicality of the concept of memory adaptiveness by providing a uniform, memory-adaptive to interval contention store/release protocol for Network Attached Disks. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Asynchronous distributed system Shared memory Adaptive algorithms Uniform protocol memory complexity Storage area network Infinitely many processes

来源：评论

学校读者我要写书评

暂无评论

memory-Constrained No-Regret Learning in Adversarial Multi-Armed Bandits

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2021年 69卷 2371-2382页

作者： Xu, Xiao Zhao, Qing Cornell Univ Sch Elect & Comp Engn Ithaca NY 14850 USA

An adversarial multi-armed bandit problem with memory constraints is studied where the memory for storing arm statistics is only in a sublinear order of the number of arms. A hierarchical learning framework that offers a sequence of operating points on the tradeoff curve between the regret order and memory complexity is developed. Its sublinear regret orders are established under both weak regret and shifting regret notions. This work appears to be the first on memory-constrained bandit problems in the adversarial setting.

关键词： memory management complexity theory Benchmark testing Stochastic processes Deep learning Games History Adversarial multi-armed bandits no-regret learning memory complexity

来源：评论

学校读者我要写书评

暂无评论

Efficient haplotype block recognition of very long and dense genetic sequences

引用

BMC BIOINFORMATICS 2014年第1期15卷 1-18页

作者： Taliun, Daniel Gamper, Johann Pattaro, Cristian European Acad Bolzano Bozen EURAC Biomed Ctr Bozen Bolzano Italy Free Univ Bozen Bolzano Bozen Bolzano Italy

Background: The new sequencing technologies enable to scan very long and dense genetic sequences, obtaining datasets of genetic markers that are an order of magnitude larger than previously available. Such genetic sequences are characterized by common alleles interspersed with multiple rarer alleles. This situation has renewed the interest for the identification of haplotypes carrying the rare risk alleles. However, large scale explorations of the linkage-disequilibrium (LD) pattern to identify haplotype blocks are not easy to perform, because traditional algorithms have at least Theta (n(2)) time and memory complexity. Results: We derived three incremental optimizations of the widely used haplotype block recognition algorithm proposed by Gabriel et al. in 2002. Our most efficient solution, called MIG(,)(++) has only Theta (n) memory complexity and, on a genome-wide scale, it omits >80% of the calculations, which makes it an order of magnitude faster than the original algorithm. Differently from the existing software, the MIG(++) analyzes the LD between SNPs at any distance, avoiding restrictions on the maximal block length. The haplotype block partition of the entire HapMap II CEPH dataset was obtained in 457 hours. By replacing the standard likelihood-based D' variance estimator with an approximated estimator, the runtime was further improved. While producing a coarser partition, the approximate method allowed to obtain the full-genome haplotype block partition of the entire 1000 Genomes Project CEPH dataset in 44 hours, with no restrictions on allele frequency or long-range correlations. These experiments showed that LD-based haplotype blocks can span more than one million base-pairs in both HapMap II and 1000 Genomes datasets. An application to the North American Rheumatoid Arthritis Consortium (NARAC) dataset shows how the MIG(++) can support genome-wide haplotype association studies. Conclusions: The MIG(++) enables to perform LD-based haplotype block recognit

关键词： Linkage Disequilibrium Haplotype Block Strong Linkage Disequilibrium memory complexity Block Partition

来源：评论

学校读者我要写书评

暂无评论

Time and space optimality of rotor-router graph exploration

引用

INFORMATION PROCESSING LETTERS 2017年第Nov.期127卷 17-20页

作者： Menc, Artur Pajak, Dominik Uznanski, Przemyslaw Wroclaw Univ Technol Fac Fundamental Problems Technol Wroclaw Poland Swiss Fed Inst Technol Dept Comp Sci Zurich Switzerland

We consider the problem of exploration of an anonymous, port-labeled, undirected graph with n nodes, m edges and diameter D, by a single mobile agent. Initially the agent does not know the graph topology nor any of the global parameters. Moreover, the agent does not know the incoming port when entering a vertex. Each vertex is endowed with memory that can be read and modified by the agent upon its visit to that node. However the agent has no operational memory i.e., it cannot carry any state while traversing an edge. In such a model at least log(2) d bits are needed at each vertex of degree d for the agent to be able to traverse each graph edge. This number of bits is always sufficient to explore any graph in time O(mD) using algorithm ROTOR-ROUTER Yanovski et al. (2003) [1]. We show that even if the available node memory is unlimited then time Omega(mD) is required in some graphs, regardless of the algorithm. This shows that ROTOR-ROUTER is asymptotically optimal in the worst-case. Secondly we show that for the case of paths, ROTOR-ROUTER attains exactly optimal time. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Distributed computing Graph exploration memory complexity

来源：评论

学校读者我要写书评

暂无评论

An empirical estimation for time and memory algorithm complexities: newly developed R package

引用

MULTIMEDIA TOOLS AND APPLICATIONS 2021年第2期80卷 2997-3015页

作者： Agenis-Nevers, Marc Bokde, Neeraj Dhanraj Yaseen, Zaher Mundher Shende, Mayur Kishor Epictr Factory Clermont Ferrand France Aarhus Univ Dept Engn Renewable Energy & Thermodynam Aarhus Denmark Ton Duc Thang Univ Sustainable Dev Civil Engn Res Grp Fac Civil Engn Ho Chi Minh City Vietnam Govt Coll Engn Nagpur Maharashtra India

When an algorithm or a program runs on a computer, it requires some resources. The complexity of an algorithm is the measure of the resources, for some input. These complexities are usually space and time. The subject of the empirical computational complexity has been studied in the research. This article introduces GuessCompx which is an R package that performs an empirical estimation on the time and memory complexities of an algorithm or a function, and provides a reliable, convenient and simple procedure for estimation process. It tests multiple increasing-sizes samples of the user's data and attempts to fit one of seven complexity functions:O(N), O(N2), O(log(N)), etc. In addition, based on the best fit procedure using leave one out-mean squared error (LOO-MSE), it predicts the full computation time and memory usage on the whole dataset. Together with this results, a plot and a significance test are returned. complexity is assessed with regard to the user's actual dataset through its size (and no other parameter). This article provides several examples demonstrating several cases (e.g., distance function, time series and custom function) and optimal parameters tuning.

关键词： Time complexity memory complexity Empirical approach R package Algorithm complexity

来源：评论

学校读者我要写书评

暂无评论

Statistical Inference With Limited memory: A Survey

IEEE JOURNAL ON SELECTED AREAS IN INFORMATION THEORY

引用

IEEE JOURNAL ON SELECTED AREAS IN INFORMATION THEORY 2024年 5卷 623-644页

作者： Berg, Tomer Ordentlich, Or Shayevitz, Ofer Tel Aviv Univ Dept Elect Engn Syst IL-6997801 Tel Aviv Israel Hebrew Univ Jerusalem Sch Comp Sci & Engn IL-91904 Jerusalem Israel

The problem of statistical inference in its various forms has been the subject of decades-long extensive research. Most of the effort has been focused on characterizing the behavior as a function of the number of available samples, with far less attention given to the effect of memory limitations on performance. Recently, this latter topic has drawn much interest in the engineering and computer science literature. In this survey paper, we attempt to review the state-of-the-art of statistical inference under memory constraints in several canonical problems, including hypothesis testing, parameter estimation, and distribution property testing/estimation. We discuss the main results in this developing field, and by identifying recurrent themes, we extract some fundamental building blocks for algorithmic construction, as well as useful techniques for lower bound derivations.

关键词： memory complexity sample complexity com- munication complexity com- munication complexity inference under memory constraints finite memory algorithms finite memory algorithms simple hypothesis testing simple hypothesis testing parameter estimation parameter estimation uniformity testing uniformity testing entropy estimation entropy estimation entropy estimation

来源：评论

学校读者我要写书评

暂无评论

Showcasing straight-line programs with memory via matrix Bruhat decomposition

引用

INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION 2024年第7期34卷 1059-1090页

作者： Niemeyer, Alice C. Popiel, Tomasz Praeger, Cheryl E. Rademacher, Daniel Rhein Westfal TH Aachen Chair Algebra & Representat Theory Pontdriesch 10-16 D-52062 Aachen Germany Monash Univ Sch Math 9 Rainforest Walk Clayton Vic 3800 Australia Univ Western Australia Ctr Math Symmetry & Computat 35 Stirling Highway Crawley WA 6009 Australia

We suggest that straight-line programs designed for algebraic computations should be accompanied by a comprehensive complexity analysis that takes into account both the number of fundamental algebraic operations needed, as well as memory requirements arising during evaluation. We introduce an approach for formalizing this idea and, as illustration, construct and analyze straight-line programs for the Bruhat decomposition of d x d matrices with determinant 1 over a finite field of order q that have length O(d2log(q)) and require storing only O(log(q)) matrices during evaluation.

关键词： Straight-Line program complexity of algorithms Bruhat decomposition memory complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：