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

query complexity of Boolean functions on the middle slice of the cube

DISCRETE APPLIED MATHEMATICS 2025年 362卷 43-49页

作者： Gerbner, Daniel Keszegh, Balazs Nagy, Daniel T. Nagy, Kartal Palvolgyi, Domotor Patkos, Balazs Wiener, Gabor HUN REN Alfred Renyi Inst Math Budapest Hungary Eotvos Lorand Univ Budapest Hungary Budapest Univ Technol & Econ Dept Comp Sci & Informat Theory Budapest Hungary

We study the query complexity on slices of Boolean functions. Among other results we show that there exists a Boolean function for which we need to query all but 7 input bits to compute its value, even if we know beforehand that the number of 0's and 1's in the input are the same, i.e., when our input is from the middle slice. This answers a question of Byramji. Our proof is non-constructive, but we also propose a concrete candidate function that might have the above property. Our results are related to certain natural discrepancy type questions that, somewhat surprisingly, have not been studied before. (c) 2024 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： query complexity Boolean function Discrepancy Game

来源：评论

学校读者我要写书评

暂无评论

On the exact quantum query complexity of MOD and EXACT functions

引用

Frontiers of Computer Science 2025年第4期19卷 91-98页

作者： Penghui YAO Zekun YE State Key Laboratory for Novel Software Technology Nanjing UniversityNanjing 210023China Hefei National Laboratory Hefei 230088China

In this paper,we consider the exact quantum query complexity of two fundamental symmetric functions.1)MOD_(m)^(n),which calculates the Hamming weight of an-bit string modulo;2)EXACT_(k,l)^(n),which determines if the Hamming weight of an-bit string is exactly k or *** these two symmetric functions have received considerable attention,their exact quantum query complexities have not been fully ***,our results are as follows:1)We design an optimal quantum query algorithm to compute MOD_(m)^(n)exactly and thus provide a tight characterization of its exact quantum query complexity,which settles a previous *** on this algorithm,we demonstrate that a broad class of symmetric functions is not evasive in the quantum model,i.e.,there exist quantum algorithms to compute these functions exactly when the number of queries is less than their input size.2)By proposing a quantum algorithm that utilizes the minimum number of queries to compute EXACT_(k,l)^(n)exactly for some specific values of k and l,we give a tight characterization of its exact quantum query complexity in these scenarios.

关键词： quantum computing query complexity symmetric functions exact algorithms evasiveness

来源：评论

学校读者我要写书评

暂无评论

Enhanced deterministic approximation algorithm for non-monotone submodular maximization under knapsack constraint with linear query complexity

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2025年第1期49卷 1-14页

作者： Pham, Canh V. Phenikaa Univ Fac Comp Sci ORLab Hanoi Vietnam

In this work, we consider the Submodular Maximization under Knapsack (SMK) constraint problem over the ground set of size n. The problem recently attracted a lot of attention due to its applications in various domains of combinatorial optimization, artificial intelligence, and machine learning. We improve the approximation factor of the fastest deterministic algorithm from 6+& varepsilon;to 5+& varepsilon;while keeping the best query complexity of O(n), where & varepsilon;>0 is a constant parameter. Our technique is based on optimizing the performance of two components: the threshold greedy subroutine and the building of two disjoint sets as candidate solutions. Besides, by carefully analyzing the cost of candidate solutions, we obtain a tighter approximation factor.

关键词： Submodular maximization Knapsack constraint Approximation algorithm query complexity

来源：评论

学校读者我要写书评

暂无评论

On the Fine-Grained query complexity of Symmetric Functions

引用

COMPUTATIONAL complexity 2025年第1期34卷 1-77页

作者： Podder, Supartha Yao, Penghui Ye, Zekun SUNY Stony Brook DEPT COMP SCI New York NY USA Nanjing Univ State Key Lab Novel Software Technol Nanjing 210023 Peoples R China Hefei Natl Lab Hefei 210023 Peoples R China

Watrous conjectured that the randomized and quantum query complexities of symmetric functions are polynomially equivalent, which was resolved by Aaronson & Ambainis (2014) and was later improved by Chailloux (2019) and Ben-David et al. (2020). This paper explores a fine-grained version of the Watrous conjecture, including the randomized and quantum algorithms with success probabilities arbitrarily close to 1/2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1/2$$\end{document}. Our contributions include the following: We analyze the optimal success probabilities of quantum and randomized query algorithms of two fundamental partial symmetric Boolean functions given a fixed number of *** establish that for any total symmetric Boolean function f\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f$$\end{document}, if a quantum algorithm uses T\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T$$\end{document} queries to compute f\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f$$\end{document} with success probability 1/2+beta\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1/2

关键词： query complexity Symmetric functions Quantum advantages Polynomial equivalence

来源：评论

学校读者我要写书评

暂无评论

query complexity of membership comparable sets

引用

THEORETICAL COMPUTER SCIENCE 2003年第1-3期302卷 467-474页

作者： Tantau, T Tech Univ Berlin Fak Elektrotech & Informat 4 D-10587 Berlin Germany Univ Rochester New York NY USA

This paper investigates how many queries to k-membership comparable sets are needed in order to decide all (k + 1)-membership comparable sets. For k greater than or equal to 2 this query complexity is at least linear and at most cubic. As a corollary, we obtain that more languages are O(log n)-membership comparable than truth-table reducible to P-selective sets. (C) 2003 Elsevier Science B.V. All rights reserved.

关键词： query complexity membership comparable P-selective

来源：评论

学校读者我要写书评

暂无评论

query complexity of mastermind variants

引用

DISCRETE MATHEMATICS 2018年第3期341卷 665-671页

作者： Berger, Aaron Chute, Christopher Stone, Matthew Yale Univ 10 Hillhouse Ave New Haven CT 06511 USA

We study variants of Mastermind, a popular board game in which the objective is sequence reconstruction. In this two-player game, the so-called codemaker constructs a hidden sequence H = (h(1), h(2), ... , h(n)) of colors selected from an alphabet A = {1, 2, ... , k} (i.e., h(i) is an element of A for all i is an element of{1, 2, ... , n}). The game then proceeds in turns, each of which consists of two parts: in turn t, the second player (the codebreaker) first submits a query sequence Q(t) = (q(1), q(2), ... , q(n)) with q(i) is an element of A for all i, and second receives feedback Delta(Q(t), H), where Delta is some agreed-upon function of distance between two sequences with n components. The game terminates when the codebreaker has determined the value of H, and the codebreaker seeks to end the game in as few turns as possible. Throughout we let f(n, k) denote the smallest integer such that the codebreaker can determine any H in f(n, k) turns. We prove three main results: First, when H is known to be a permutation of {1, 2, ... , n}, we prove that f(n, n) >= n - log log n for all sufficiently large n. Second, we show that Knuth's Minimax algorithm identifies any H in at most nk queries. Third, when feedback is not received until all queries have been submitted, we show that f(n, k) = Omega(n log k). (C) 2017 Elsevier B.V. All rights reserved.

关键词： Combinatorial games Mastermind query complexity

来源：评论

学校读者我要写书评

暂无评论

query complexity of Least Absolute Deviation Regression via Robust Uniform Convergence 34

Query Complexity of Least Absolute Deviation Regression via ...

引用

Conference on Learning Theory (COLT)

作者： Chen, Xue Derezinski, Michal George Mason Univ Fairfax VA 22030 USA Univ Calif Berkeley Berkeley CA 94720 USA

Consider a regression problem where the learner is given a large collection of d-dimensional data points, but can only query a small subset of the real-valued labels. How many queries are needed to obtain a 1+ epsilon relative error approximation of the optimum? While this problem has been extensively studied for least squares regression, little is known for other losses. An important example is least absolute deviation regression (l(1) regression) which enjoys superior robustness to outliers compared to least squares. We develop a new framework for analyzing importance sampling methods in regression problems, which enables us to show that the query complexity of least absolute deviation regression is Theta(d/epsilon(2)) up to logarithmic factors. We further extend our techniques to show the first bounds on the query complexity for any l(p) loss with p is an element of (1, 2). As a key novelty in our analysis, we introduce the notion of robust uniform convergence, which is a new approximation guarantee for the empirical loss. While it is inspired by uniform convergence in statistical learning, our approach additionally incorporates a correction term to avoid unnecessary variance due to outliers. This can be viewed as a new connection between statistical learning theory and variance reduction techniques in stochastic optimization, which should be of independent interest.

关键词： robust regression query complexity uniform convergence Lewis weight sampling

来源：评论

学校读者我要写书评

暂无评论

query complexity of Approximate Nash Equilibria 14

Query Complexity of Approximate Nash Equilibria

引用

46th Annual ACM Symposium on Theory of Computing (STOC)

作者： Babichenko, Yakov CALTECH 1200 E Calif Blvd MC 305-16 Pasadena CA 91125 USA

We study the query complexity of approximate notions of Nash equilibrium in games with a large number of players n and a constant number of actions m. Our main result states that even for constant epsilon, the query c... 详细信息

ISBN: (纸本)9781450327107

关键词： Approximate Nash Equilibrium query complexity Fixed Point Rate of Convergence Adaptive Dynamics

来源：评论

学校读者我要写书评

暂无评论

Upper Bounds on Quantum query complexity Inspired by the Elitzur-Vaidman Bomb Tester

引用

THEORY OF COMPUTING 2016年 12卷

作者： Lin, Cedric Yen-Yu Lin, Han-Hsuan Univ Maryland Joint Ctr Quantum Informat & Comp Sci College Pk MD 20742 USA Natl Univ Singapore Ctr Quantum Technol Singapore Singapore

Inspired by the Elitzur-Vaidman bomb testing problem (1993), 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) = Theta(Q(f)(2)). This result gives a new method to derive upper bounds on quantum query complexity: we give a method of finding bomb query algorithms from classical algorithms, which then provide non-constructive upper bounds on Q(f) = Theta(root B(f)). Subsequently, we were able to give explicit quantum algorithms matching our new bounds. We apply this method to the single-source shortest paths problem on unweighted graphs, obtaining an algorithm with O(n(1.5)) quantum query complexity, improving the best known algorithm of O(n(1.5)logn) (Durr et al. 2006, Furrow 2008). Applying this method to the maximum bipartite matching problem gives an algorithm with O(n(1.75)) quantum query complexity, improving the best known (trivial) O(n(2)) upper bound.

关键词： algorithms query complexity quantum algorithms quantum query complexity graph algorithms Elitzur-Vaidman bomb tester adversary method maximum bipartite matching

来源：评论

学校读者我要写书评

暂无评论

Lower bounds for randomized and quantum query complexity using Kolmogorov arguments

引用

SIAM JOURNAL ON COMPUTING 2008年第1期38卷 46-62页

作者： Laplante, Sophie Magniez, Frederic Univ Paris 11 CNRS LRI F-91405 Orsay France

We prove a very general lower bound technique for quantum and randomized query complexity that is easy to prove as well as to apply. To achieve this, we introduce the use of Kolmogorov complexity to query complexity. Our technique generalizes the weighted and unweighted methods of Ambainis and the spectral method of Barnum, Saks, and Szegedy. As an immediate consequence of our main theorem, it can be shown that adversary methods can only prove lower bounds for Boolean functions f in O(min(root nC(0)(f), root nC(1)(f))), where C-0, C-1 is the certificate complexity and n is the size of the input.

关键词： quantum computing lower bounds query complexity adversary method Kolmogorov complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：