Questions tagged [query-complexity]
The query-complexity tag has no summary.
58 questions
0
votes
0
answers
64
views
Break finding on a graph
Given a graph with $n$ nodes where some of the edges are defective and two nodes $u,v$ of the graph which are not connected by a path of non defective edges, I am allowed to query any two nodes $a,b$ ...
- 358
0
votes
0
answers
59
views
What data structure minimizes the amount of combine operation in point updates and range queries (and having the smallest leading constant)?
Suppose you have an array $a$ of $n$ elements in a set $X$, and an associative binary operation $\circ \ \colon X \times X \rightarrow X$, that can be evaluated in constant time, but is costly (e.g. $...
- 1
1
vote
0
answers
57
views
Worst and average case time complexity of a k-dimensional prefix search in a kd-trie?
TL;DR
What is the time complexity of a $k$-dimensional prefix search in a "$k$d-trie" (not a "kd-tree") in the worst and average cases ?
Here, the $k$d-trie is a standard trie that ...
- 21
0
votes
0
answers
99
views
(nearly)-Linear size data structure for log-time "origin-pegged" d-dimensional range queries Q = ([0, x_1], [0, x_2], ..., [0, x_d]) possible?
Given n points, is there a data structure of size at most $O(n.log\, n)$ that can answer to an "origin-pegged" $d$-dimensional range query $Q = ([0, x_1], [0, x_2], ..., [0, x_d])$ in log or ...
- 21
3
votes
0
answers
115
views
Collapse of query and oracle hierarchies
Let ${\tt QH}$ stand for the Query Hierarchy, defined as the union of all classes ${\tt P}^{{\tt NP}[k]}$, of problems solvable by polynomial time machines making at most $k$ queries to ${\tt NP}$ and ...
- 120
-2
votes
1
answer
130
views
What is really the difference between membership queries and "querying in i.i.d?
I'm struggling at finding the difference between algorithms that use i.i.d random queries then request their labels and algorithms that use membership queries.
Membership queries allow the learner to ...
- 122
4
votes
0
answers
91
views
distinguishments between query complexity of membership oracles and standard time complexity
Many combinatorial optimization problems can be described as follows. We are given a set system $(E,I)$, where $I \subseteq 2^E$ and a weight function $w: E \rightarrow \mathbb{N}$. The goal is to ...
- 432
5
votes
1
answer
133
views
Independent set queries with preprocessing
Suppose we have a sparse undirected graph $G = (V, E)$ with $|E| = O(|V|)$, and we want to process it and then answer queries of the following type: given a set $A$, is it an independent set in the ...
- 792
14
votes
1
answer
482
views
What is (a reasonable conjectured lower bound on) the query complexity of solving an $n\times n$ system of linear equations given space $O(n)$?
I am faced with the following problem:
A uniformly random $n \times n$ matrix $M$ over a finite field $\mathbb{F}$ is sampled. The algorithm has oracle access to the matrix entries, and each query to ...
- 828
1
vote
1
answer
188
views
On motivation towards study of width parameters beyond treewidth
Many width parameters are invented to capture the tractability of CSP (and its equivalent problem, conjunctive queries (CQ) evaluation): treewidth, hypertree width, generalized hypertree width, ...
- 125
6
votes
1
answer
284
views
What is the impact of encodings of sparse structures on the complexity of the model checking problem?
Some preliminaries first.
Consider a purely-relational structure (a.k.a. database) $\mathfrak{A} = (A, R_1^{\mathfrak{A}}, \ldots, R_{|\tau|}^{\mathfrak{A}})$ over some finite signature $\tau = \{ R_1,...
- 1,462
1
vote
1
answer
140
views
Composition theorem for randomized communication complexity
I am currently organizing the literature of composition theorem, and I found the paper by https://www.research.cs.rutgers.edu/~troyjlee/Composition.pdf, in their theorem 5, I find
$$ R_{1/4} (f \circ ...
- 113
6
votes
1
answer
170
views
Complexity of approximating a real function using queries
Consider the following computational problem, where $I$ is the real interval $[-1,1]$:
There is a monotonically-increasing function $f: I\to I$. You are allowed to access it only through queries of ...
- 2,324
1
vote
0
answers
60
views
Non-rigid isomorphic structures
In many of the problems trying to solve hidden shift over some objects like graphs mainly the rigid classes are considered. For eg. in this and this isomorphism problem restricted over rigid graphs is ...
- 387
7
votes
2
answers
433
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}$ ...
- 39.4k