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

Lower bounds for the query complexity of equilibria in Lipschitz games

THEORETICAL COMPUTER SCIENCE 2023年第1期962卷

作者： Goldberg, Paul W. Katzman, Matthew J. Univ Oxford Dept Comp Sci Oxford England

Nearly a decade ago, Azrieli and Shmaya introduced the class of & lambda;-Lipschitz games in which every player's payoff function is & lambda;-Lipschitz with respect to the actions of the other players. They showed that such games admit ⠃-approximate pure Nash equilibria for certain settings of ⠃ and & lambda;. They left open, however, the question of how hard it is to find such an equilibrium. In this work, we develop a query-efficient reduction from more general games to Lipschitz games. We use this reduction to show a query lower bound for any randomized algorithm finding ⠃-approximate pure Nash equilibria of n-player, binary -action, & lambda;-Lipschitz games that is exponential in n & lambda;/⠃. In addition, we introduce "Multi -Lipschitz games," a generalization involving player-specific Lipschitz values, and provide a reduction from finding equilibria of these games to finding equilibria of Lipschitz games, showing that the value of interest is the average of the individual Lipschitz parameters. Finally, we provide an exponential lower bound on the deterministic query complexity of finding ⠃-approximate Nash equilibria of n-player, m-action, & lambda;-Lipschitz games for strong values of ⠃, motivating the consideration of explicitly randomized algorithms in the above results.& COPY;2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

关键词： query complexity Lipschitz games Nash equilibrium

来源：评论

学校读者我要写书评

暂无评论

A Strong XOR Lemma for Randomized query complexity

引用

THEORY OF COMPUTING 2023年第1期19卷 1-14页

作者： Brody, Joshua Kim, Jae Tak Lerdputtipongporn, Peem Srinivasulu, Hariharan Swarthmore Coll Dept Comp Sci Swarthmore PA 19081 USA Google Mountain View CA USA Carnegie Mellon Univ Stat Dept Pittsburgh PA USA Palantir Technol New York NY USA

We give a strong direct sum theorem for computing XORk degrees g, the XOR of k instances of the partial Boolean function g. Specifically, we show that for every g and every k >= 2, the randomized query complexity of computing the XOR of k instances of g satisfies Re(XORk degrees g) = O(k Rek(g)), where Re(f) denotes the expected number of queries made by the most efficient randomized algorithm computing f with e error. This matches the naive success amplification upper bound and answers a conjecture of Blais and Brody (CCC'19).As a consequence of our strong direct sum theorem, we give a total function g for which R(XORk degrees g) = O(k log(k) center dot R(g)), where R(f) is the number of queries made by the most efficient randomized algorithm computing f with 1/3 error. This answers a question from Ben-David et al. (RANDOM'20).

关键词： lower bounds query complexity direct sum

来源：评论

学校读者我要写书评

暂无评论

Optimal Composition Theorem for Randomized query complexity

引用

THEORY OF COMPUTING 2023年第1期19卷 1-35页

作者： Gavinsky, Dmytro Lee, Troy Santha, Miklos Sanyal, Swagato Czech Acad Sci Inst Math Zitna 25 Prague 115 67 Czech Republic Univ Technol Sydney Ctr Quantum Software & Informat Ultimo Australia Univ Paris Cite CNRS IRIF F-75013 Paris France Natl Univ Singapore CQT Singapore Singapore IIT Kharagpur Dept Comp Sci & Engn Kharagpur India

For any set S, any relation F subset of {0, 1}(n) x S and any partial Boolean function, defined on a subset of {0, 1}(m), we show that R-1/3 (f o g(n)) is an element of Omega (R-4/9(f) center dot root R-1/3(g)), where R-epsilon(center dot) stands for the bounded-error randomized query complexity with error at most epsilon, and f o g(n) subset of ({0, 1}(m))(n) x S denotes the composition of 5 with = instances of g. This result is new even in the special case when S = {0, 1} and g is a total function. We show that the new composition theorem is optimal for the general case of relations: A relation f(0) and a partial Boolean function g(0) are constructed, such that R-4/9 (f(0)) is an element of Theta(root n), R-1/3(g(0)) is an element of Theta (n) and R-1/3(f(0) o g(0)(n)) is an element of Theta (n). The theorem is proved via introducing a new complexity measure, max-conflict complexity, denoted by chi(center dot). Its investigation shows that (chi) over bar (g) is an element of Omega(R-1/3(g)) for any partial Boolean function g and (R-1/3(f o g(n)) is an element of Omega(R-4/9(f) center dot (chi) over bar (g)) for any relation f, which readily implies the composition statement. It is further shown that (chi) over bar (g) is always at least as large as the sabotage complexity of g (introduced by Ben-David and Kothari in 2016).

关键词： query complexity randomized decision tree composed function lower bound

来源：评论

学校读者我要写书评

暂无评论

Upper bounds on quantum query complexity inspired by the elitzur-vaidman bomb tester 15

Upper bounds on quantum query complexity inspired by the eli...

引用

Proceedings of the 30th Conference on Computational complexity

作者： Cedric Yen-Yu Lin Han-Hsuan Lin Massachusetts Institute of Technology Cambridge MA

ISBN: (纸本)9783939897811

Inspired by the Elitzur-Vaidman bomb testing problem [19], we introduce a new query complexity model, which we call bomb query complexity B(f). We investigate its relationship with the usual quantum query complexity Q(f), and show that B(f) = Θ(Q(f)2).This result gives a new method to upper bound the quantum query complexity: we give a method of finding bomb query algorithms from classical algorithms, which then provide nonconstructive upper bounds on [EQUATION]. We subsequently were able to give explicit quantum algorithms matching our upper bound method. We apply this method on the single-source shortest paths problem on unweighted graphs, obtaining an algorithm with O(n1.5) quantum query complexity, improving the best known algorithm of [EQUATION] [21]. Applying this method to the maximum bipartite matching problem gives an O(n1.75) algorithm, improving the best known trivial O(n2) upper bound.

关键词： adversary method quantum algorithms query complexity elitzur-vaidman bomb tester maximum bipartite matching

来源：评论

学校读者我要写书评

暂无评论

Optimal separation and strong direct sum for randomized query complexity 19

Optimal separation and strong direct sum for randomized quer...

引用

Proceedings of the 34th Computational complexity Conference

作者： Eric Blais Joshua Brody University of Waterloo ON Canada Swarthmore College

ISBN: (纸本)9783959771160

We establish two results regarding the query complexity of bounded-error randomized algorithms. Bounded-error separation theorem. There exists a total function f : {0, 1}n → {0, 1} whose ∈-error randomized query complexity satisfies [EQUATION].Strong direct sum theorem. For every function f and every k ≥ 2, the randomized query complexity of computing k instances of f simultaneously satisfies [EQUATION].As a consequence of our two main results, we obtain an optimal superlinear direct-sum-type theorem for randomized query complexity: there exists a function f for which R(fk) = [EQUATION]. This answers an open question of Drucker (2012). Combining this result with the query-to-communication complexity lifting theorem of Göös, Pitassi, and Watson (2017), this also shows that there is a total function whose public-coin randomized communication complexity satisfies Rcc (fk) = [EQUATION], answering a question of Feder, Kushilevitz, Naor, and Nisan (1995).

关键词： decision trees query complexity communication complexity

来源：评论

学校读者我要写书评

暂无评论

Settling the query complexity of non-adaptive junta testing 17

Settling the query complexity of non-adaptive junta testing

引用

Proceedings of the 32nd Computational complexity Conference

作者： Xi Chen Rocco A. Servedio Li-Yang Tan Erik Waingarten Jinyu Xie Columbia University Toyota Technological Institute

ISBN: (纸本)9783959770408

We prove that any non-adaptive algorithm that tests whether an unknown Boolean function f: {0, 1}n → {0, 1} is a k-junta or ε-far from every k-junta must make [EQUATION](k3/2 /ε) many queries for a wide range of parameters k and ε. Our result dramatically improves previous lower bounds from [12, 38], and is essentially optimal given Blais's non-adaptive junta tester from [7], which makes [EQUATION](k3/2)/ε queries. Combined with the adaptive tester of [8] which makes O(k log k + k/ε) queries, our result shows that adaptivity enables polynomial savings in query complexity for junta testing.

关键词： property testing query complexity juntas

来源：评论

学校读者我要写书评

暂无评论

High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial query complexity

引用

JOURNAL OF THE ACM 2017年第2期64卷 11-11页

作者： Kopparty, Swastik Meir, Or Ron-Zewi, Noga Saraf, Shubhangi Rutgers State Univ Dept Math 110 Frelinghuysen Rd Piscataway NJ 08854 USA Rutgers State Univ Dept Comp Sci 110 Frelinghuysen Rd Piscataway NJ 08854 USA Univ Haifa Dept Comp Sci Abba Khoushy Ave 199 IL-3498838 Haifa Israel Ben Gurion Univ Negev Dept Comp Sci IL-8499000 Beer Sheva Israel

Locally correctable codes (LCCs) and locally testable codes (LTCs) are error-correcting codes that admit local algorithms for correction and detection of errors. Those algorithms are local in the sense that they only query a small number of entries of the corrupted codeword. The fundamental question about LCCs and LTCs is to determine the optimal tradeoff among their rate, distance, and query complexity. In this work, we construct the first LCCs and LTCs with constant rate, constant relative distance, and sub-polynomial query complexity. Specifically, we show that there exist LCCs and LTCs with block length n, constant rate (which can even be taken arbitrarily close to 1), and constant relative distance, whose query complexity is exp( (O) over tilde (root log n)) (for LCCs) and (log n)(O(log log n)) (for LTCs). In addition to having small query complexity, our codes also achieve better tradeoffs between the rate and the relative distance than were previously known to be achievable by LCCs or LTCs. Specifically, over large (but constant size) alphabet, our codes approach the Singleton bound, that is, they have almost the best-possible relationship between their rate and distance. Over the binary alphabet, our codes meet the Zyablov bound. Such tradeoffs between the rate and the relative distance were previously not known for any o(n) query complexity. Our results on LCCs also immediately give locally decodable codes with the same parameters.

关键词： Locally correctable codes locally decodable codes locally testable codes asymptotically good codes query complexity singleton bound zyablov bound

来源：评论

学校读者我要写书评

暂无评论

Nearly Optimal Separations Between Communication (or query) complexity and Partitions 31

Nearly Optimal Separations Between Communication (or Query) ...

引用

31st Conference on Computational complexity (CCC)

作者： Ambainis, Andris Kokainis, Martins Kothari, Robin Univ Latvia Fac Comp Riga Latvia MIT Ctr Theoret Phys Cambridge MA 02139 USA

ISBN: (纸本)9783959770088

We show a nearly quadratic separation between deterministic communication complexity and the logarithm of the partition number, which is essentially optimal. This improves upon a recent power 1.5 separation of Gees, Pitassi, and Watson (FOCS 2015). In query complexity, we establish a nearly quadratic separation between deterministic (and even randomized) query complexity and subcube partition complexity, which is also essentially optimal. We also establish a nearly power 1.5 separation between quantum query complexity and subcube partition complexity, the first superlinear separation between the two measures. Lastly, we show a quadratic separation between quantum query complexity and one-sided subcube partition complexity. Our query complexity separations use the recent cheat sheet framework of Aaronson, Ben-David, and Kothari. Our query functions are built up in stages by alternating function composition with the cheat sheet construction. The communication complexity separation follows from "lifting" the query separation to communication complexity.

关键词： query complexity Communication complexity Subcube Partition complexity Partition Bound

来源：评论

学校读者我要写书评

暂无评论

Database Size Estimation by query Performance - A complexity Aspect

Database Size Estimation by Query Performance - A Complexity...

引用

5th IEEE/ACM International Conference on Utility and Cloud Computing (UCC)

作者： Zhou, Ye Chi, Chi-Hung Tsinghua Univ Dept Comp Sci & Technol Beijing 100084 Peoples R China CSIRO Intelligent Sensing & Syst Lab Hobart Australia

ISBN: (纸本)9780769548623;9781467344326

Many techniques have been proposed to database size estimation. However, the emergency of cloud computing introduces new opportunities along with new challenges. In cloud, a monitoring proxy can be set up by service provider due to the ownership of cloud infrastructure. The collected data allows for service provider to estimate the size of database which may be a black-box to them. We claim that the relationship between query performance and data size can be captured by a complexity function. One can leverage such function to estimate table size if given query execution time. In this paper, we propose a fine grained framework called Database Size Estimation based on complexity (DSEC) to estimate the size of databases from the perspective of service provider. In particular, we argue that only a small fraction of tables impact service performance significantly, which are referred to as "important tables". We illustrate "important table" locating process on three typical benchmarks: RUBiS, RUBBoS and TPC-W. Finally, we describe extensive experiments on TPC-W (the most challenging one) to evaluate the effectiveness and efficiency of DSEC in various scenarios.

关键词： query performance database size estimation query complexity

来源：评论

学校读者我要写书评

暂无评论

Computing approximate roots of monotone functions

引用

JOURNAL OF complexity 2025年 88卷

作者： Hollender, Alexandros Lawrence, Chester Segal-Halevi, Erel Univ Oxford All Souls Coll Oxford England Ariel Univ Ariel Israel

We are given a value-oracle for a d-dimensional function f that satisfies the conditions of Miranda's theorem, and therefore has a root. Our goal is to compute an approximate root using a number of evaluations that is polynomial in the number of accuracy digits. For d = 1 this is always possible using the bisection method, but for d > 2 this is impossible in general. We show that, if d = 2 and f satisfies a single monotonicity condition, then the number of required evaluations is polynomial in the accuracy. The same holds if d >= 3 and f satisfies some particular d(2) - d monotonicity conditions. We show that, if d = 2 and f satisfies a single monotonicity condition, then the number of required evaluations is polynomial in the accuracy. The same holds if d >= 3 and f satisfies some particular d(2) - d monotonicity conditions. In contrast, if even two of these monotonicity conditions are missing, then the required number of evaluations might be exponential. As an example application, we show that approximate roots of monotone functions can be used for approximate envy-free cake- cutting. (c) 2025 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http:// ***/licenses/by/4.0/).

关键词： Root finding Fixed point Value oracle query complexity Cake cutting

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：