The tag has no wiki summary.

learn more… | top users | synonyms

13
votes
0answers
281 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 ...
13
votes
1answer
272 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 ...
7
votes
2answers
165 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 ...
7
votes
2answers
260 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 ...
10
votes
0answers
176 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 ...
22
votes
1answer
413 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 ...
12
votes
1answer
291 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 ...
6
votes
2answers
430 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 ...
10
votes
1answer
271 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 ...
15
votes
2answers
351 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 ...
1
vote
0answers
100 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$ ...
16
votes
3answers
283 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 ...
7
votes
1answer
253 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 ...
7
votes
0answers
175 views

Are the minimal quantum and classical span programs the same?

A span program is a linear-algebraic way of specifying a boolean function introduced here which has found recent application in quantum query complexity. A span program for a function $f: \{0,1\}^n ...
1
vote
0answers
261 views

Discovering a graph with minimal oracle queries

I have a transitive DAG G which is a subgraph of an unknown DAG R. (The nodes are the same in G and R, but R may have edges not in G.) I can determine the presence of a given edge in R by an oracle ...
4
votes
1answer
157 views

Trade off between width and depth of free BDDs for total functions

Terminology A binary decision diagram is a directed acyclic graph with one source (root), and two sinks ($A$ and $B$). Each non-sink nodes is labeled by an integer $i \in \{1,...,n\}$ and has ...
11
votes
1answer
610 views

Algorithm for optimizing decision trees

Background A binary decision tree $T$ is a rooted tree where each internal node (and root) is labeled by an index $j \in \{1,..., n\}$ such that no path from root to leaf repeats an index, the leafs ...
17
votes
3answers
474 views

Trade off between time and query complexity

Working directly with time complexity or circuit lower bounds is scary. Hence, we develop tools like query complexity (or decision-tree complexity) to get a handle on lower bounds. Since each query ...
17
votes
1answer
409 views

Using the extra power of the negative adversary method

The negative adversary method ($ADV^\pm$) is an SDP that characterizes quantum query complexity. It is a generalization of the widely used adversary method ($ADV$), and overcomes the two barriers that ...
9
votes
3answers
405 views

Bounding the gap between quantum and deterministic query complexity

Although exponential separations between bounded-error quantum query complexity ($Q(f)$) and deterministic query complexity ($D(f)$) or bounded-error randomized query complexity ($R(f)$) are known, ...
10
votes
1answer
344 views

Span programs, witness size, and certificate complexity

A span program is a linear-algebraic way of specifying a boolean function introduced here. Recently, this model was used to show that the negative adversary method provides a tight characterization ...
7
votes
2answers
322 views

Quantum query complexity and certificate complexity

A certificate for an input $x$ is a subset of bits $S \subseteq \{1,...,n\}$ such that for all inputs $y$, $(\forall i \in S \quad y_i = x_i) \rightarrow f(y) = f(x)$. Then $C_x(f)$ is the minimum ...
9
votes
1answer
489 views

Lower bounds on the Threshold function

In decision tree complexity of a boolean function, a very well know lower bound method is to find a (approximate) polynomial that represents the function. Paturi gave a characterization for symmetric ...
8
votes
2answers
333 views

Finding out a set by intersection comparison

The following problem recently emerged from my research and I would like to ask if anyone knows if this problem was considered before or has heard of anything that might be related. The general ...