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

complexity of Equivalence and Learning for Multiplicity Tree Automata

JOURNAL OF MACHINE LEARNING RESEARCH 2015年第1期16卷 2465-2500页

作者： Marusic, Ines Worrell, James Univ Oxford Dept Comp Sci Parks Rd Oxford OX1 3QD England

We consider the query and computational complexity of learning multiplicity tree automata in Angluin's exact learning model. In this model, there is an oracle, called the Teacher, that can answer membership and equivalence queries posed by the Learner. Motivated by this feature, we first characterise the complexity of the equivalence problem for multiplicity tree automata, showing that it is logspace equivalent to polynomial identity testing. We then move to query complexity, deriving lower bounds on the number of queries needed to learn multiplicity tree automata over both fixed and arbitrary fields. In the latter case, the bound is linear in the size of the target automaton. The best known upper bound on the query complexity over arbitrary fields derives from an algorithm of Habrard and Oncina (2006), in which the number of queries is proportional to the size of the target automaton and the size of a largest counterexample, represented as a tree, that is returned by the Teacher. However, a smallest counterexample tree may already be exponential in the size of the target automaton. Thus the above algorithm has query complexity exponentially larger than our lower bound, and does not run in time polynomial in the size of the target automaton. We give a new learning algorithm for multiplicity tree automata in which counterexamples to equivalence queries are represented as DAGs. The query complexity of this algorithm is quadratic in the target automaton size and linear in the size of a largest counterexample. In particular, if the Teacher always returns DAG counterexamples of minimal size then the query complexity is quadratic in the target automaton size-almost matching the lower bound, and improving the best previously-known algorithm by an exponential factor.

关键词： exact learning query complexity multiplicity tree automata Hankel matrices DAG representations of trees polynomial identity testing

来源：评论

学校读者我要写书评

暂无评论

Optimal Parallel Quantum query Algorithms

引用

ALGORITHMICA 2017年第2期79卷 509-529页

作者： Jeffery, Stacey Magniez, Frederic de Wolf, Ronald CALTECH Inst Quantum Informat & Matter Pasadena CA 91125 USA Univ Paris Diderot Sorbonne Paris Cite CNRS IRIF F-75205 Paris France CWI QuSoft Amsterdam Netherlands Univ Amsterdam Amsterdam Netherlands

We study the complexity of quantum query algorithms that make p queries in parallel in each timestep. This model is in part motivated by the fact that decoherence times of qubits are typically small, so it makes sense to parallelize quantum algorithms as much as possible. We show tight bounds for a number of problems, specifically Theta((n/p)(2/3)) p-parallel queries for element distinctness and Theta((n/p)(k/(k+ 1))) for k-sum. Our upper bounds are obtained by parallelized quantum walk algorithms, and our lower bounds are based on a relatively small modification of the adversary lower bound method, combined with recent results of Belovs et al. on learning graphs. We also prove some general bounds, in particular that quantum and classical p-parallel query complexity are polynomially related for all total functions f when p is small compared to f's block sensitivity.

关键词： Quantum algorithms query complexity Parallel algorithms Lower bounds

来源：评论

学校读者我要写书评

暂无评论

Short PCPPs verifiable in polylogarithmic time with O(1) queries

引用

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE 2009年第3-4期56卷 313-338页

作者： Mie, Thilo Univ Karlsruhe TH Inst Kryptog & Sicherheit D-76131 Karlsruhe Germany

In this paper we show for every pair language L subset of {0, 1}* x {0, 1}* in NTIME(T) for some non-decreasing function T : Z(+) -> Z(+) there is a PCPP-verifier such that the following holds. In time poly(vertical bar x vertical bar, log vertical bar y vertical bar, log T(vertical bar x vertical bar + vertical bar y vertical bar)) it decides the membership of a purported word (x, y) by reading the explicit input x entirely and querying the implicit input y and the auxiliary proof of length T(vertical bar x vertical bar + vertical bar y vertical bar) . poly log T(vertical bar x vertical bar + vertical bar y vertical bar) in a constant number of positions.

关键词： PCP PCPP Verifier Time complexity query complexity

来源：评论

学校读者我要写书评

暂无评论

Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds

引用

COMPUTATIONAL complexity 2019年第2期28卷 145-183页

作者： Meir, Or Wigderson, Avi Univ Haifa Dept Comp Sci IL-3498838 Haifa Israel Inst Adv Study Olden Lane Princeton NJ 08540 USA

Consider a random sequence of n bits that has entropy at least n-k, where k<<n . A commonly used observation is that an average coordinate of this random sequence is close to being uniformly distributed, that is... 详细信息

Consider a random sequence of n bits that has entropy at least n-k, where k<query approximate to other coordinates of the sequence, even if the adversary is non-deterministic. This implies corresponding results for decision trees and certificates for Boolean *** an application of this result, we prove a new result on depth-3 circuits, which recovers as a direct corollary the known lower bounds for the parity and majority functions, as well as a lower bound on sensitive functions due to Boppana (Circuits Inf Process Lett 63(5):257-261, 1997). An interesting feature of this proof is that it works in the framework of Karchmer and Wigderson (SIAM J Discrete Math 3(2):255-265, 1990), and, in particular, it is a top-down proof (Hastad et al. in Computat Complex 5(2):99-112, 1995). Finally, it yields a new kind of a random restriction lemma for non-product distributions, which may be of independent interest.

关键词： Certificate complexity Circuit complexity Circuit complexity lower bounds Decision tree complexity Information theoretic query complexity Sensitivity

来源：评论

学校读者我要写书评

暂无评论

Faster Counting and Sampling Algorithms Using Colorful Decision Oracle

引用

ACM TRANSACTIONS ON COMPUTATION THEORY 2024年第2期16卷 1-19页

作者： Bhattacharya, Anup Bishnu, Arijit Ghosh, Arijit Mishra, Gopinath Natl Inst Sci Educ & Res Bhubaneswar India Indian Stat Inst Kolkata India Natl Univ Singapore Kent Ridge Campus Singapore Singapore

In this work, we consider d-Hyperedge Estimation and d-Hyperedge Sample problems that deal with estimation and uniform sampling of hyperedges in a hypergraph H(U (H), F(H)) in the query complexity framework, where U (H) denotes the set of vertices and F(H) denotes the set of hyperedges. The oracle access to the hypergraph is called Colorful Independence Oracle (CID), which takes d (non-empty) pairwise disjoint subsets of vertices A(1),..., A(d) subset of U (H) as input and answers whether there exists a hyperedge in H having exactly one vertex in each A(i) for all i is an element of{1, 2,..., d}. Apart from the fact that d-Hyperedge Estimation and d-Hyperedge Sample problems with CID oracle access seem to be nice combinatorial problems, Dell et al. [SODA'20 & SICOMP'22] established that decision vs. counting complexities of a number of combinatorial optimization problems can be abstracted out as d-Hyperedge Estimation problem with a CID oracle access. The main technical contribution of this article is an algorithm that estimates m = vertical bar F(H)vertical bar with (m) over cap such that 1/C-d log(d-1) n <= (m) over cap /m <= C-d log(d-1) n by using at most C-d log(d+2) n CID queries, where n denotes the number of vertices in the hypergraph H and C-d is a constant that depends only on d. Our result, when coupled with the framework proposed by Dell et al. (SODA'20 & SICOMP'22), leads to implies improved bounds for (1 +/- epsilon)-approximation (where epsilon is an element of(0, 1)) for the following fundamental problems: Edge Estimation using the Bipartite Independent Set (BIS) query. We improve the bound obtained by Beame et al. (ITCS'18 & TALG'20). Triangle Estimation using the Tripartite Independent Set (TIS) query. Currently, Dell et al.'s result gives the best bound for the case of triangle estimation in general graphs (SODA'20 & SICOMP'22). The previous best bound for the case of graphs with low co-degree (co-degree of a graph is the maximum number of triangl

关键词： Group query hyperedge estimation query complexity

来源：评论

学校读者我要写书评

暂无评论

Quantum and Randomised Algorithms for Non-linearity Estimation

引用

ACM TRANSACTIONS ON QUANTUM COMPUTING 2021年第2期2卷 1–27页

作者： Bera, Debajyoti Tharrmashastha, Sapv IIIT Delhi Okhla Phase 3 New Delhi 110020 India

Non-linearity of a Boolean function indicates how far it is from any linear function. Despite there being several strong results about identifying a linear function and distinguishing one froma sufficiently non-linear function, we found a surprising lack of work on computing the non-linearity of a function. The non-linearity is related to the Walsh coefficient with the largest absolute value;however, the naive attempt of picking the maximum after constructing a Walsh spectrum requires Theta(2(n)) queries to an n-bit function. We improve the scenario by designing highly efficient quantum and randomised algorithms to approximate the non-linearity allowing additive error, denoted lambda, with query complexities that depend polynomially on lambda. We prove lower bounds to show that these are not very far from the optimal ones. The number of queries made by our randomised algorithm is linear in n, already an exponential improvement, and the number of queries made by our quantum algorithm is surprisingly independent of n. Our randomised algorithm uses a Goldreich-Levin style of navigating all Walsh coefficients and our quantum algorithm uses a clever combination of Deutsch-Jozsa, amplitude amplification and amplitude estimation to improve upon the existing quantum versions of the Goldreich-Levin technique.

关键词： Boolean function non-linearity quantum algorithm query complexity

来源：评论

学校读者我要写书评

暂无评论

USE OF PSYCHOLOGICAL EXPERIMENTATION AS AN AID TO DEVELOPMENT OF A query LANGUAGE

引用

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING 1977年第3期3卷 218-229页

作者： REISNER, P IBM CORP RES LABSSAN JOSECA 95114

This paper describes a series of psychological experiments used to test a new data base query language. The intent is to make psychological testing of a language part of the design and development process. By testing a language while it is still under development, features that require changing can bs identified and the changes made.

关键词： Data Base Languages Human Factors Psychological Testing Software Error Classification query complexity query Language Development query Language Testing

来源：评论

学校读者我要写书评

暂无评论

Hierarchy Theorems for Property Testing

引用

COMPUTATIONAL complexity 2012年第1期21卷 129-192页

作者： Goldreich, Oded Krivelevich, Michael Newman, Ilan Rozenberg, Eyal Weizmann Inst Sci Dept Comp Sci IL-76100 Rehovot Israel Tel Aviv Univ Sch Math Sci IL-69978 Tel Aviv Israel Univ Haifa Dept Comp Sci IL-31999 Haifa Israel Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

Referring to the query complexity of property testing, we prove the existence of a rich hierarchy of corresponding complexity classes. That is, for any relevant function q, we prove the existence of properties that have testing complexity I similar to(q). Such results are proven in three standard domains often considered in property testing: generic functions, adjacency predicates describing (dense) graphs, and incidence functions describing bounded-degree graphs. While in two cases, the proofs are quite straightforward, and the techniques employed in the case of the dense graph model seem significantly more involved. Specifically, problems that arise and are treated in the latter case include (1) the preservation of distances between graph under a blow-up operation and (2) the construction of monotone graph properties that have local structure.

关键词： Property testing hierarchy theorems query complexity graph properties monotone graph properties graph blow-up one-sided versus two-sided error adaptivity versus non-adaptivity

来源：评论

学校读者我要写书评

暂无评论

A note on envy-free cake cutting with polynomial valuations

引用

INFORMATION PROCESSING LETTERS 2015年第2期115卷 93-95页

作者： Branzei, Simina Aarhus Univ Dept Comp Sci DK-8200 Aarhus Denmark

The cake cutting problem models the fair allocation of a heterogeneous divisible resource among multiple players. The central fairness criterion is envy-freeness and a major open question in this domain is the design of a bounded protocol that can compute an envy-free allocation of the cake for any number of players. The only existing finite envy-free cake cutting protocol for any number of players, designed by Brams and Taylor [4], has the property that its runtime can be made arbitrarily large by setting up the valuation functions of the players appropriately. Moreover, there is no closed formula that relates the valuation functions to the number of queries required by the protocol. In this note we show that when the valuations can be represented as polynomial functions, there exists a protocol in the standard query model that is much simpler conceptually and has a runtime bound depending on the maximum degree over all polynomials. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Algorithms Cake cutting query complexity Envy-freeness

来源：评论

学校读者我要写书评

暂无评论

Almost optimal query algorithm for hitting set using a subset query

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2023年第1期137卷 50-65页

作者： Bishnu, Arijit Ghosh, Arijit Kolay, Sudeshna Mishra, Gopinath Saurabh, Saket Indian Stat Inst Kolkata India Indian Inst Technol Kharagpur Kharagpur India Univ Warwick Coventry England HBNI Inst Math Sci Chennai India

In this paper, we focus on HITTING-SET, a fundamental problem in combinatorial optimization, through the lens of sublinear time algorithms. Given access to the hypergraph through a subset query oracle in the query model, we give sublinear time algorithms for HITTING-SET with almost tight parameterized query complexity. In parameterized query complexity, we estimate the number of queries to the oracle based on the parameter k, the size of the HITTING-SET. The subset query oracle we use in this paper is called Generalized d-partite Independent Set query oracle (GPIS) and it was introduced by Bishnu et al. (ISAAC'18). GPIS is a generalization to hypergraphs of the Bipartite Independent Set query oracle (BIS) introduced by Beame et al. (ITCS'18 and TALG'20) for estimating the number of edges in graphs. Since its introduction GPIS query oracle has been used for estimating the number of hyperedges independently by Dell et al.(SODA'20 and SICOMP'22) and Bhattacharya et al. (STACS'22), and for estimating the number of triangles in a graph by Bhattacharya et al. (ISAAC'19 and TOCS'21). Formally, GPIS is defined as follows: GPIS oracle for a d-uniform hypergraph H takes as input d pairwise disjoint non-empty subsets A(1),..., A(d) of vertices in Hand answers whether there is a hyperedge in Hthat intersects each set A(i), where i is an element of{1, 2,..., d}. For d = 2, the GPIS oracle is nothing but BIS oracle. We show that d-Hitting-Set, the hitting set problem for d-uniform hypergraphs, can be solved using (O) over tilde (d)(k(d) log n) GPIS queries. Additionally, we also showed that d-DECISION-HITTING-SET, the decision version of d-HITTING-SET can be solved with (O) over tilde (d) (min {k(d) log n, k(2d2)} GPIS queries. We complement these parameterized upper bounds with an almost matching parameterized lower bound that states that any algorithm that solves d-Decision HITTING-SET requires Omega ((k+d d)) GPIS queries. (c) 2023 Elsevier Inc. All rights reserved.

关键词： query complexity Subset queries Hitting set Parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：