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

35th Conference on Learning Theory (COLT)

作者： Liu, Xizhi Mukherjee, Sayan Univ Illinois Dept Math Stat & Comp Sci Chicago IL 60680 USA Univ Warwick Math Inst Coventry CV4 7AL W Midlands England Univ Warwick DIMAP Coventry CV4 7AL W Midlands England Blueqat Res Shibuya Tokyo Japan

Given a partition of a graph into connected components, the membership oracle asserts whether any two vertices of the graph lie in the same component or not. We prove that for n >= k >= 2, learning the components of an n-vertex hidden graph with k components requires at least (k-1)n-((k)(2)) membership queries. Our result improves on the best known information-theoretic bound of Omega(n log k) queries, and exactly matches the query complexity of the algorithm introduced by Reyzin and Srivastava (2007) for this problem. Additionally, we introduce an oracle, with access to which one can learn the number of components of G in asymptotically fewer queries than learning the full partition, thus answering another question posed by the same authors. Lastly, we introduce a more applicable version of this oracle, and prove asymptotically tight bounds of (Theta) over tilde (m) queries for both learning and verifying an m-edge hidden graph G using it.

关键词： graph learning graph reconstruction query complexity

来源：评论

学校读者我要写书评

暂无评论

The query complexity of sampling from strongly log-concave distributions in one dimension 35

The query complexity of sampling from strongly log-concave d...

引用

35th Conference on Learning Theory (COLT)

作者： Chewi, Sinho Gerber, Patrik Lu, Chen Le Gouic, Thibaut Rigollet, Philippe MIT Cambridge MA 02139 USA Aix Marseille Univ CNRS Cent Marseille I2M Marseille France

We establish the first tight lower bound of Omega(log log k) on the query complexity of sampling from the class of strongly log-concave and log-smooth distributions with condition number k in one dimension. Whereas existing guarantees for MCMC-based algorithms scale polynomially in k, we introduce a novel algorithm based on rejection sampling that closes this doubly exponential gap.

关键词： sampling query complexity lower bound rejection sampling

来源：评论

学校读者我要写书评

暂无评论

query complexity of Correlated Equilibrium

引用

ACM Transactions on Economics and Computation 2015年第4期3卷 1–9页

作者： Yakov Babichenko Siddharth Barman California Institute of Technology

We study lower bounds on the query complexity of determining correlated equilibrium. In particular, we consider a query model in which an n-player game is specified via a black box that returns players' utilities at pure action profiles. In this model, we establish that in order to compute a correlated equilibrium, any deterministic algorithm must query the black box an exponential (in n) number of times.

关键词： Correlated equilibrium computation of equilibrium query complexity

来源：评论

学校读者我要写书评

暂无评论

An algorithmic argument for nonadaptive query complexity lower bounds on advised quantum computation (Extended abstract)

引用

29th International Symposium on Mathematical Foundations of Computer Science

作者： Nishimura, H Yamakami, T Trent Univ Comp Sci Program Peterborough ON K9J 7B8 Canada

ISBN: (纸本)3540228233

This paper employs a powerful argument, called an algorithmic argument, to prove lower bounds of the quantum query complexity of a multiple-block ordered search problem, which is a natural generalization of the ordered search problem. Apart from much studied polynomial and adversary methods for quantum query complexity lower bounds, our argument shows that the multiple-block ordered search needs a large number of nonadaptive oracle queries on a black-box model of quantum computation that is also supplemented with advice. Our argument is also applied to the notions of computational complexity theory: quantum truth-table reducibility and quantum truth-table autoreducibility.

关键词： algorithmic argument query complexity nonadaptive query advice quantum computation

来源：评论

学校读者我要写书评

暂无评论

On query complexity Measures and Their Relations for Symmetric Functions 10th

On Query Complexity Measures and Their Relations for Symmetr...

引用

10th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM)

作者： Mittal, Rajat Nair, Sanjay S. Patro, Sunayana Indian Inst Technol Kanpur India Int Inst Informat Technol Hyderabad India

ISBN: (纸本)9783031522123;9783031522130

The main reason for query model's prominence in complexity theory and quantum computing is the presence of concrete lower bounding techniques: polynomial and adversary method. There have been considerable efforts to give lower bounds using these methods, and to compare/relate them with other measures based on the decision tree. We explore the value of these lower bounds on quantum query complexity and their relation with other decision tree based complexity measures for the class of symmetric functions, arguably one of the most natural and basic sets of Boolean functions. We show an explicit construction for the dual of the positive adversary method and also of the square root of private coin certificate game complexity for any total symmetric function. This shows that the two values cannot be distinguished for any symmetric function. Additionally, we show that the recently introduced measure of spectral sensitivity gives the same value as both positive adversary and approximate degree for every total symmetric Boolean function. Further, we look at the quantum query complexity of Gap Majority, a partial symmetric function. It has gained importance recently in regard to understanding the composition of randomized query complexity. We characterize the quantum query complexity of Gap Majority and show a lower bound on noisy randomized query complexity (Ben-David and Blais, FOCS 2020) in terms of quantum query complexity.

关键词： Computational complexity Quantum Physics query complexity

来源：评论

学校读者我要写书评

暂无评论

Quadratic Memory is Necessary for Optimal query complexity in Convex Optimization: Center-of-Mass is Pareto-Optimal 36

Quadratic Memory is Necessary for Optimal Query Complexity i...

引用

36th Annual Conference on Learning Theory (COLT)

作者： Blanchard, Moise Zhang, Junhui Jaillet, Patrick MIT Cambridge MA 02139 USA

We give query complexity lower bounds for convex optimization and the related feasibility problem. We show that quadratic memory is necessary to achieve the optimal oracle complexity for first-order convex optimization with deterministic algorithms. In particular, this shows that center-of-mass cutting-planes algorithms in dimension d which use (O) over tilde (d(2)) memory and (O) over tilde (d) queries are Pareto-optimal for both convex optimization and the feasibility problem, up to logarithmic factors. Precisely, building upon techniques introduced in [23], we prove that to minimize 1-Lipschitz convex functions over the unit ball to 1/d(4) accuracy, any deterministic first-order algorithms using at most d(2-delta) bits of memory must make (Omega) over tilde (d(1+delta/3)) queries, for any delta is an element of[0, 1]. For the feasibility problem, in which an algorithm only has access to a separation oracle, we show a stronger tradeoff: for at most d(2-delta) memory, the number of queries required is (Omega) over tilde (d(1+delta)). This resolves a COLT 2019 open problem of Woodworth and Srebro.

关键词： Convex optimization feasibility problem first-order methods cutting-planes center-of-mass memory lower bounds query complexity

来源：评论

学校读者我要写书评

暂无评论

query complexity of Boolean functions on slices

引用

DISCRETE MATHEMATICS 2024年第6期347卷

作者： Byramji, Farzan Indian Inst Technol Kanpur India Univ Calif San Diego La Jolla CA 92093 USA

The kth slice ([n]) of the Boolean cube {0, 1}n is the set of all n -bit strings with Hamming k weight k. We study the deterministic query complexity of Boolean functions on slices of the Boolean cube. We show that there exists a function on the balanced slice ( [n]) requiring n/2 n - O (log log n) queries. We observe that there is an explicit function on the balanced slice requiring n - O (log n) queries based on independent sets in Johnson graphs. We also consider the maximum query complexity on constant-weight slices and how it relates to Ramsey theorems. (c) 2024 Elsevier B.V. All rights reserved.

关键词： query complexity Slice Boolean cube

来源：评论

学校读者我要写书评

暂无评论

The Partition Bound for Classical Communication complexity and query complexity

The Partition Bound for Classical Communication Complexity a...

引用

25th Annual IEEE Conference on Computational complexity

作者： Jain, Rahul Klauck, Hartmut Natl Univ Singapore Ctr Quantum Technol Singapore 117548 Singapore Nanyang Technol Univ SPMS Ctr Quantum Technol Nanyang Singapore

ISBN: (纸本)9780769540603

We describe new lower bounds for randomized communication complexity and query complexity which we call the partition bounds. They are expressed as the optimum value of linear programs. For communication complexity we show that the partition bound is stronger than both the rectangle/corruption bound and the gamma(2)/generalized discrepancy bounds. In the model of query complexity we show that the partition bound is stronger than the approximate polynomial degree and classical adversary bounds. We also exhibit an example where the partition bound is quadratically larger than the approximate polynomial degree and adversary bounds.

关键词： Communication complexity query complexity Lower Bounds Partition Bound Linear Programming

来源：评论

学校读者我要写书评

暂无评论

Randomized query complexity of Sabotaged and Composed Functions

引用

THEORY OF COMPUTING 2018年 14卷 1-27页

作者： Ben-David, Shalev Kothari, Robin Univ Maryland Joint Ctr Quantum Informat & Comp Sci College Pk MD 20742 USA Microsoft Res Quantum Architectures & Computat Grp QuArC Redmond WA USA

We study the composition question for bounded-error randomized query complexity: Is R(f circle g) = Omega(R(f) R(g)) for all Boolean functions f and g? We show that inserting a simple Boolean function h, whose query complexity is only Theta(logR(g)), in between f and g allows us to prove R(f circle h circle g) = Omega(R(f) R(h) R(g)). We prove this using a new lower bound measure for randomized query complexity we call randomized sabotage complexity, RS(f). Randomized sabotage complexity has several desirable properties, such as a perfect composition theorem, RS (f circle g) >= RS(f) RS(g), and a composition theorem with randomized query complexity, R(f circle g) = Omega(R(f) RS(g)). It is also a quadratically tight lower bound for total functions and can be quadratically superior to the partition bound, the best known general lower bound for randomized query complexity. Using this technique we also show implications for lifting theorems in communication complexity. We show that a general lifting theorem for zero-error randomized protocols implies a general lifting theorem for bounded-error protocols.

关键词： randomized algorithms query complexity composition theorems

来源：评论

学校读者我要写书评

暂无评论

Separations in query complexity Based on Pointer Functions

引用

JOURNAL OF THE ACM 2017年第5期64卷 32-32页

作者： Ambainis, Andris Balodis, Kaspars Belovs, Aleksandrs Lee, Troy Santha, Miklos Smotrovs, Juris Univ Latvia Fac Comp Raina Blvd 19 LV-1586 Riga Latvia Nanyang Technol Univ Sch Phys & Math Sci Singapore Singapore Ctr Quantum Technol Singapore Singapore MajuLab Singapore Singapore SPMS 21 Nanyang Link Singapore 637371 Singapore Univ Paris Diderot IRIF CNRS Case 7014 F-75205 Paris France

In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total Boolean function is given by the function f on n = 2(k) bits defined by a complete binary tree of NAND gates of depth k, which achieves R-0(f) = O(D(f)(0.7)(537. )(. .)). We show that this is false by giving an example of a total Boolean function f on n bits whose deterministic query complexity is (Omega) over tilde (n) while its zero-error randomized query complexity is (O) over tilde(root n). We further show that the quantum query complexity of the same function is (O) over tilde (n(1/4)), giving the first example of a total function with a super-quadratic gap between its quantum and deterministic query complexities. We also construct a total Boolean function g on n variables that has zero-error randomized query complexity Omega(n/log(n)) and bounded-error randomized query complexity R(g) = ((O) over tilde root n). This is the first superlinear separation between these two complexity measures. The exact quantum query complexity of the same function is (Q) over tilde (E)(g) = (O) over tilde(root n). These functions show that the relations D(f) = O(R-1(f)(2)) and R-0(f) = (O) over tilde (R(f)(2)) are optimal, up to polylogarithmic factors. Further variations of these functions give additional separations between other query complexity measures: a cubic separation between Q and R-0, a 3/2-power separation between Q(E) and R, and a 4th-power separation between approximate degree and bounded-error randomized query complexity. All of these examples are variants of a function recently introduced by Goos, Pitassi, and Watson, which they used to separate the unambiguous 1-certificate complexity from deterministic query complexity and to resolve the famous Clique versus Independent Set problem in communication complexity.

关键词： Decision trees quantum algorithms query complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：