Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2110.13012 · Society for Industrial and Applied Mathematics eBooks

Parameterized Convexity Testing

Abhiruk Lahiri, Ilan Newman, Nithin M. Varma

Published Jan 1, 2022• 1 citation
arXivHTMLPDF

Abstract

In this work, we develop new insights into the fundamental problem of convexity testing of real-valued functions over the domain [n]. Specifically, we present a nonadaptive algorithm that, given inputs ε ∊ (0,1), s ∊ ℕ, and oracle access to a function, ε-tests convexity in O(log(s)/ε), where s is an upper bound on the number of distinct discrete derivatives of the function. We also show that this bound is tight. Since s ≤ n, our query complexity bound is at least as good as that of the optimal convexity tester (Ben Eliezer; ITCS 2019) with complexity ; our bound is strictly better when s = o(n). The main contribution of our work is to appropriately parameterize the complexity of convexity testing to circumvent the worst-case lower bound (Belovs et al.; SODA 2020) of expressed in terms of the input size and obtain a more efficient algorithm.

DOI
10.1137/1.9781611977066.12

Related papers

Optimal Quantum Junta Testing without Inverse Queries

Jinge Bao, Minbo Gao, Penghui Yao

We study the query complexity of testing quantum juntas. Given an unknown $n$-qubit unitary or quantum channel, the goal is to decide whether it acts nontrivially on at most $k$ qubits or is $\varepsilon$-far from every such operation. For unitaries, we consider the forward-only model, where the tester has access to $U$, but not to $U^\dagger$ or controlled-$U$. We give tight bounds for both unitary and channel junta testing. For sufficiently large $k$, $n \ge 2k$, and a broad range of $\varepsilon$, both problems have query complexity $Θ\left(k/(\varepsilon^2\log k)\right)$. Our upper bounds are achieved by simple nonadaptive testers using product inputs and single-qubit measurements. For junta channels, this closes the gap by Bao and Yao (COLT 23, TPAMI 2025) between an $\widetilde{O}(k)$ upper bound and a $\widetildeΩ(\sqrt{k})$ lower bound at constant $\varepsilon$, establishing the optimal $Θ(k/\log k)$ query complexity. At the heart of both bounds is a strong connection between quantum junta testing and classical support-size testing. For the upper bounds, we reduce quantum junta testing to a generalized support-size problem for distributions over random subsets, and develop a new tester with improved sample complexity. For the lower bounds, we proceed in the reverse direction, reducing classical support-size testing to quantum junta testing through a phase-masked hard ensemble and showing that forward quantum queries can be exactly classicalized on average. Together, these reductions identify support-size testing as the classical core of quantum junta testing and yield matching lower bounds. At constant $\varepsilon$, they also give a separation between $Θ(k/\log k)$ forward queries and $\widetilde{O}(\sqrt{k})$ queries with inverse access.

quant-pharXiv:2609.37926•Sep 30, 2026•1 citation

An Optimal Algorithm for Certifying Monotone Functions

Meghal Gupta, Naren Sarayu Manoj

Given query access to a monotone function f: {0,1}n → {0,1} with certificate complexity C(f) and an input x*, we design an algorithm that outputs a size-C (f) subset of x* certifying the value of f(x*). Our algorithm makes O (C(f) · log n) queries to f, which matches the information-theoretic lower bound for this problem and resolves the main open question posed in the STOC 2022 paper of Blanc, Koch, Lange, and Tan [BKLT22].

arXiv:2204.01224•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2023•1 citation

Separable Non-convex Underestimators for Binary Quadratic Programming

Christoph Buchheim, Emiliano Traversi

Lecture notes in computer science•Jan 1, 2013•8 citations

A o(n) monotonicity tester for boolean functions over the hypercube

Deeparnab Chakrabarty, Comandur Seshadhri

Given oracle access to a Boolean function f:{0,1}n -> {0,1}, we design a randomized tester that takes as input a parameter ε>0, and outputs Yes if the function is monotonically non-increasing, and outputs No with probability >2/3, if the function is ε-far from being monotone, that is, f needs to be modified at ε-fraction of the points to make it monotone. Our non-adaptive, one-sided tester makes ~O(n5/6ε-5/3) queries to the oracle.

ACM Symposium on Theory of Computing (STOC)•May 28, 2013•37 citations

Time-Space Tradeoffs and Query Complexity in Statistics, Coding Theory, and Quantum Computing

Widad Machmouchi

Computational complexity is the field that studies the computational resources needed by algorithms to correctly solve computational problems. In this thesis, we derive lower bounds on the computational complexity of different problems for different classes of algorithms. The computational resources we consider are the running time, the memory usage and the input query complexity; i.e., the number of positions in the input that the algorithm reads. While deriving upper bounds involves constructing algorithms that run efficiently in their computational resources, lower bounds for a computational problem establish limits on how fast or space-efficient any algorithm solving that problem can be. We consider two main themes of lower bounds: time-space tradeoffs and query complexity lower bounds. Time-space tradeoffs define a relation between the running time and space of any algorithm solving a certain problems. They give a complete picture of the hardness of a problem by deriving a lower bound on one resource when the other is limited. Query complexity measures the depth of a decision tree computing the problem. We derive several lower bounds and upper bounds for different problems on different types of classical computational models and on quantum computers, where the queries to the input are represented by quantum operations operating on the qubits of the algorithm: 1) We derive the largest time-space tradeoff known for a randomized algorithm solving an explicit problem. We consider the pointer jumping problem, also known as the outdegree-1 graph accessibility problem and derive a T in Ω(n log(n/S) log log(n/S)) time-space tradeoff for any randomized oblivious algorithm computing it. Oblivious algorithms have the property that the sequence of operations performed is independent of the value of the input. We derive a similar lower bound for randomized oblivious algorithms with boolean inputs. 2) Frequency moments and order statistics are attributes computed on a sequence of numbers and are extremely relevant in various data analysis settings. We consider computing several copies of these functions on overlapping sequences of numbers by considering a window of a fixed length and sliding it over the input; these versions are called sliding-window versions of these functions. We give hardness separations between the sliding-window versions of these statistics. On one hand, we give a TS in Ω(n 2 ) lower bounds for any algorithm computing sliding-window frequency moments. To complement our lower bound, we give a TS in O(n 2 log c n) comparison-based algorithm for sliding-window frequency moments. On the other hand we describe a T 2 S in O(n 3 log c n) algorithm for sliding-window element distinctness. For order statistics, we derive a similar lower bound of TS in Ω(n 2 ) for any algorithm computing a sliding-widow version of the median, while for the sliding window version of maximum (and minimum), we construct an O(n log n)-time, logarithmic space algorithm. 3) We study the increase in complexity on quantum computers when considering sliding-window frequency moments. We show that quantum computers do not require the same increase in complexity as their classical counterparts by constructing a quantum algorithm for sliding-window version of the zero th frequency moments running in time O(n 3/2 ) and logarithmic space, thus beating the classical lower bound for this problem. 4) In the area of error-correcting codes, we study the query complexity of error detection and correction algorithms. We prove that linear codes over large alphabets that are small in size and concentrated in terms of their codeword weights have testers and correctors that require only a constant number of queries to a word received across a noisy channel. Such codes are called locally-testable and self-correctable. As random codes of small size have the property that their codeword weights are concentrated in a small range of values, they are also locally-testable and self-correctable with high probability. 5) For linear codes with information-efficient encoding, we study the tradeoff between the time and space of their encoders, and their error-correction property. We derive properties on generator matrices of asymptotically good linear codes that guarantee an optimal time-space tradeoff of TS in Ω(n 2 ) for any algorithm encoding them. Moreover, we prove a first step in an approach to establish these properties for all generator matrices of such codes. 6) To compare classical computers to their quantum counterparts, we consider the query complexity of quantum algorithms computing frequency moments and the onto function that takes as input a function and determines whether it is surjective. We prove that any quantum computer computing the onto function or the parity of the zero th frequency moment requires a linear number of queries to the input. Since the onto function with boolean inputs has a simple polynomial-size, constant-depth circuit, we obtain an almost linear lower bound on the query complexity of AC 0 , a special class of circuits that have polynomial size, constant depth and unbounded fan-in for their gates.

•Jul 25, 2013•0 citations

The Power of Many Samples in Query Complexity.

Andrew Bassilakis, Andrew Drucker, Mika Göös +3 more

The randomized query complexity 𝖱(f) of a boolean function f: {0,1}ⁿ → {0,1} is famously characterized (via Yao’s minimax) by the least number of queries needed to distinguish a distribution 𝒟₀ over 0-inputs from a distribution 𝒟₁ over 1-inputs, maximized over all pairs (𝒟₀,𝒟₁). We ask: Does this task become easier if we allow query access to infinitely many samples from either 𝒟₀ or 𝒟₁? We show the answer is no: There exists a hard pair (𝒟₀,𝒟₁) such that distinguishing 𝒟₀^∞ from 𝒟₁^∞ requires Θ(𝖱(f)) many queries. As an application, we show that for any composed function f∘g we have 𝖱(f∘g) ≥ Ω(fbs(f)𝖱(g)) where fbs denotes fractional block sensitivity.

Electronic colloquium on computational complexity•Jan 1, 2020•0 citations
In this work, we develop new insights into the fundamental problem of convexity testing of real-valued functions over the domain [n]. Specifically, we present a nonadaptive algorithm that, given inputs ε ∊ (0,1), s ∊ ℕ, and oracle access to a function, ε-tests convexity in O(log(s)/ε), where s is an upper bound on the number of distinct discrete derivatives of the function. We also show that this bound is tight. Since s ≤ n, our query complexity bound is at least as good as that of the optimal convexity tester (Ben Eliezer; ITCS 2019) with complexity ; our bound is strictly better when s = o(n). The main contribution of our work is to appropriately parameterize the complexity of convexity testing to circumvent the worst-case lower bound (Belovs et al.; SODA 2020) of expressed in terms of the input size and obtain a more efficient algorithm.
We study the query complexity of testing quantum juntas. Given an unknown nnn-qubit unitary or quantum channel, the goal is to decide whether it acts nontrivially on at most kkk qubits or is ε\varepsilonε-far from every such operation. For unitaries, we consider the forward-only model, where the tester has access to UUU, but not to U†U^\daggerU† or controlled-UUU. We give tight bounds for both unitary and channel junta testing. For sufficiently large kkk, n≥2kn \ge 2kn≥2k, and a broad range of ε\varepsilonε, both problems have query complexity Θ(k/(ε2log⁡k))Θ\left(k/(\varepsilon^2\log k)\right)Θ(k/(ε2logk)). Our upper bounds are achieved by simple nonadaptive testers using product inputs and single-qubit measurements. For junta channels, this closes the gap by Bao and Yao (COLT 23, TPAMI 2025) between an O~(k)\widetilde{O}(k)O(k) upper bound and a Ω~(k)\widetildeΩ(\sqrt{k})Ω(k​) lower bound at constant ε\varepsilonε, establishing the optimal Θ(k/log⁡k)Θ(k/\log k)Θ(k/logk) query complexity. At the heart of both bounds is a strong connection between quantum junta testing and classical support-size testing. For the upper bounds, we reduce quantum junta testing to a generalized support-size problem for distributions over random subsets, and develop a new tester with improved sample complexity. For the lower bounds, we proceed in the reverse direction, reducing classical support-size testing to quantum junta testing through a phase-masked hard ensemble and showing that forward quantum queries can be exactly classicalized on average. Together, these reductions identify support-size testing as the classical core of quantum junta testing and yield matching lower bounds. At constant ε\varepsilonε, they also give a separation between Θ(k/log⁡k)Θ(k/\log k)Θ(k/logk) forward queries and O~(k)\widetilde{O}(\sqrt{k})O(k​) queries with inverse access.
Computational complexity is the field that studies the computational resources needed by algorithms to correctly solve computational problems. In this thesis, we derive lower bounds on the computational complexity of different problems for different classes of algorithms. The computational resources we consider are the running time, the memory usage and the input query complexity; i.e., the number of positions in the input that the algorithm reads. While deriving upper bounds involves constructing algorithms that run efficiently in their computational resources, lower bounds for a computational problem establish limits on how fast or space-efficient any algorithm solving that problem can be. We consider two main themes of lower bounds: time-space tradeoffs and query complexity lower bounds. Time-space tradeoffs define a relation between the running time and space of any algorithm solving a certain problems. They give a complete picture of the hardness of a problem by deriving a lower bound on one resource when the other is limited. Query complexity measures the depth of a decision tree computing the problem. We derive several lower bounds and upper bounds for different problems on different types of classical computational models and on quantum computers, where the queries to the input are represented by quantum operations operating on the qubits of the algorithm: 1) We derive the largest time-space tradeoff known for a randomized algorithm solving an explicit problem. We consider the pointer jumping problem, also known as the outdegree-1 graph accessibility problem and derive a T in Ω(n log(n/S) log log(n/S)) time-space tradeoff for any randomized oblivious algorithm computing it. Oblivious algorithms have the property that the sequence of operations performed is independent of the value of the input. We derive a similar lower bound for randomized oblivious algorithms with boolean inputs. 2) Frequency moments and order statistics are attributes computed on a sequence of numbers and are extremely relevant in various data analysis settings. We consider computing several copies of these functions on overlapping sequences of numbers by considering a window of a fixed length and sliding it over the input; these versions are called sliding-window versions of these functions. We give hardness separations between the sliding-window versions of these statistics. On one hand, we give a TS in Ω(n 2 ) lower bounds for any algorithm computing sliding-window frequency moments. To complement our lower bound, we give a TS in O(n 2 log c n) comparison-based algorithm for sliding-window frequency moments. On the other hand we describe a T 2 S in O(n 3 log c n) algorithm for sliding-window element distinctness. For order statistics, we derive a similar lower bound of TS in Ω(n 2 ) for any algorithm computing a sliding-widow version of the median, while for the sliding window version of maximum (and minimum), we construct an O(n log n)-time, logarithmic space algorithm. 3) We study the increase in complexity on quantum computers when considering sliding-window frequency moments. We show that quantum computers do not require the same increase in complexity as their classical counterparts by constructing a quantum algorithm for sliding-window version of the zero th frequency moments running in time O(n 3/2 ) and logarithmic space, thus beating the classical lower bound for this problem. 4) In the area of error-correcting codes, we study the query complexity of error detection and correction algorithms. We prove that linear codes over large alphabets that are small in size and concentrated in terms of their codeword weights have testers and correctors that require only a constant number of queries to a word received across a noisy channel. Such codes are called locally-testable and self-correctable. As random codes of small size have the property that their codeword weights are concentrated in a small range of values, they are also locally-testable and self-correctable with high probability. 5) For linear codes with information-efficient encoding, we study the tradeoff between the time and space of their encoders, and their error-correction property. We derive properties on generator matrices of asymptotically good linear codes that guarantee an optimal time-space tradeoff of TS in Ω(n 2 ) for any algorithm encoding them. Moreover, we prove a first step in an approach to establish these properties for all generator matrices of such codes. 6) To compare classical computers to their quantum counterparts, we consider the query complexity of quantum algorithms computing frequency moments and the onto function that takes as input a function and determines whether it is surjective. We prove that any quantum computer computing the onto function or the parity of the zero th frequency moment requires a linear number of queries to the input. Since the onto function with boolean inputs has a simple polynomial-size, constant-depth circuit, we obtain an almost linear lower bound on the query complexity of AC 0 , a special class of circuits that have polynomial size, constant depth and unbounded fan-in for their gates.
The randomized query complexity 𝖱(f) of a boolean function f: {0,1}ⁿ → {0,1} is famously characterized (via Yao’s minimax) by the least number of queries needed to distinguish a distribution 𝒟₀ over 0-inputs from a distribution 𝒟₁ over 1-inputs, maximized over all pairs (𝒟₀,𝒟₁). We ask: Does this task become easier if we allow query access to infinitely many samples from either 𝒟₀ or 𝒟₁? We show the answer is no: There exists a hard pair (𝒟₀,𝒟₁) such that distinguishing 𝒟₀^∞ from 𝒟₁^∞ requires Θ(𝖱(f)) many queries. As an application, we show that for any composed function f∘g we have 𝖱(f∘g) ≥ Ω(fbs(f)𝖱(g)) where fbs denotes fractional block sensitivity.