# Questions tagged [query-complexity]

The tag has no usage guidance.

45 questions
Filter by
Sorted by
Tagged with
47 views

### Query complexity for functions $f\colon\left\{0,1\right\}^n\to\left\{0,1\right\}^m$

I'm studying query complexity and I'm trying to understand Bernstein-Vazirani's problem (https://en.wikipedia.org/wiki/Bernstein%E2%80%93Vazirani_algorithm) and Simon's problem (https://en.wikipedia....
168 views

### Quantum evasiveness conjecture?

A property of simple $n$-vertex graphs is said to be evasive if its deterministic query complexity is exactly maximal, $\binom{n}{2}$ (that is, the best algorithm must query all $\binom{n}{2}$ ...
82 views

145 views

135 views

### decision tree complexity and query complexity

I want good sources for starting with decision tree complexity and query complexity , what papers to start with ? what book chapters to read ? I already seen arora and barak book and I begin to read ...
141 views

### Tolerance parameter of statistical query model and adaptivity

It seems that the reasonable assumption for the tolerance parameter of statistical query model is roughly $1/\sqrt{n}$, which is obtained from concentration inequalities (see, e.g., Definition 2.3 of ...
142 views

### Does MCMC belong to the statistical query model?

It is known that a wide range of algorithms fall into the statistical query (SQ) learning model by Michael Kearns. Examples include k-means, logistic regression, naive Bayes (NB), SVM, ICA, PCA, ...
417 views

### Information complexity of query algorithms?

Information complexity has been a very useful tool in communication complexity, mainly used to lower bound the communication complexity of distributed problems. Is there an analogue of information ...
154 views

### What are the most fundamental metrics (criterions) of database performance?

I'm a student working on my thesis in database theory and looking for some research in the field of formal models of database performance and couldn't find any works in this area. I'm interested: what ...
421 views

### How can one find the “hard” probability distribution on the input for recursive boolean functions?

Update: Since, it seems there is no progress regarding this question, any idea, conjecture, hunch, or advice is welcome. For example, are there any partial or incomplete results? What are the main ...
794 views

### Las Vegas vs Monte Carlo randomized decision tree complexity

Background: Decision tree complexity or query complexity is a simple model of computation defined as follows. Let $f:\{0,1\}^n\to \{0,1\}$ be a Boolean function. The deterministic query complexity of ...
193 views

### Delegating all of the work to the prover in $\mathcal{MA}$ protocols

An $\mathcal{MA}$ communication complexity protocol is communication complexity protocol that starts with an omniscient prover that sends a proof (that depends on the the specific input of the players,...
336 views

### Are provable quantum speed-ups possible for classes larger than NP?

In the oracle query model quantum computers can provably achieve a quadratic speed-up over any classical randomized computer [Grover, BBBV]. Are similar speed-ups provably possible for higher levels ...
263 views

### Are there distribution properties which are “maximally” hard to test?

A distribution testing algorithm for a distribution property P (which is just some subset of all distributions over [n]) is allowed access to samples according to some distribution D, and is required ...
478 views

### Natural, untestable graph properties

In graph property testing, an algorithm queries a target graph for the presence or absence of edges and needs to determine whether the target either has a certain property or is $\epsilon$-far from ...
398 views

### Can quantum algorithms with exponential speed-up be rederived using span-programs?

The general adversary lower-bound is now known to characterize quantum query complexity due to breakthrough work by Reichardt et al. The same line of work also establishes connections to the span ...
623 views

### Rigorous proof that a random function and a random permutation cannot be distinguished in polynomial time

I have a background in number theory and I'm trying to learn how to reason rigorously about algorithms. I'm reading chapter 2 of Katz and Lindell's Introduction to Modern Cryptography. Show that no ...
536 views

### Lower bounds for learning in the membership query and counterexample model

Dana Angluin (1987; pdf) defines a learning model with membership queries and theory queries (counterexamples to a proposed function). She shows that a regular language that is represented by a ...
477 views

### Reconstructing a tree from separator queries

Suppose $T$ is an constant-degree tree whose structure we do not know. The problem is to output the tree $T$ by asking queries of the form: "Does the node $x$ lie on the path from node $a$ to node $b$?...
148 views

### Is there a lower bound for the decisional Grover search problem?

What is known about the decisional version of the search problem? By decisional version of the search problem, I mean the problem in which you wish to determine whether there are $0$, or exactly $t$ ...
360 views

### Models of computation strictly between classical and quantum in terms of query complexity

It is well known quantum computers are strictly more powerful than their classical counterparts in terms of query complexity. Are there other models (natural or artificial) that are strictly ...
283 views

### Trade off between time and query complexity for total functions

This is a continuation of an earlier question on the trade off between time and query complexity. By a trade off we consider the following two types of algorithms: The best query algorithm: this ...
193 views