Skip to main content
5 votes

Are there distribution properties which are "maximally" hard to test?

Sorry for unearthing this post -- it is quite old, but I figured having it answered may not be that bad an idea. First, it looks like you performed your Chernoff bound with some slightly odd setting ...
Clement C.'s user avatar
  • 4,481
5 votes

Quantum evasiveness conjecture?

Since the quantum query complexity typically denotes the bounded-error quantum query complexity, there's some ambiguity. A more precise question could be: "What is the quantum query complexity to ...
smapers's user avatar
  • 849
5 votes
Accepted

What's the proof of this lemma by Hajnal about the randomized query complexity of monotone graph properties?

I sent an email to P├ęter Hajnal, and he kindly confirmed that the bound in the lemma should be $\Omega(\frac{\Delta_L(G)}{\lceil \delta_L(G) \rceil} n)$.
William Hoza's user avatar
  • 1,743
4 votes
Accepted

The SQ argument in Balazs Szorenyi's paper

This is a standard adversary argument, not very different from adversary arguments taught in undergraduate algorithms courses. If you are unfamiliar with such arguments, then you can check out these ...
Sasho Nikolov's user avatar
4 votes

Complexity of approximating a real function using queries

Not a complete answer, but hopefully a good starting point. It is very instructive to (always!) first consider the discrete analog of your question. If $X$ is some set and $f:X\to\{0,1\}$, what is the ...
Aryeh's user avatar
  • 10.6k
4 votes
Accepted

Independent set queries with preprocessing

If the graph is uniformly sparse in the sense that every subgraph with $n$ vertices contains at most $d \cdot n$ edges for some small $d$, then degeneracy ordering could be exploited to have $O(|E|)$ ...
Laakeri's user avatar
  • 1,821
4 votes
Accepted

What is the impact of encodings of sparse structures on the complexity of the model checking problem?

I don't know of any natural logic, but the following is in any case a logic for which the combined complexity of the model-checking problem is different for matrix and list encodings. First, we know ...
Reijo Jaakkola's user avatar
3 votes

On motivation towards study of width parameters beyond treewidth

It is not hard to see that if a class of queries has arity bounded by $a$ and hypertree width bouded by $k$, then it will also have treewidth bounded by $a\cdot k$. Indeed, any bag in a hypertree ...
holf's user avatar
  • 2,174
3 votes

Quantum evasiveness conjecture?

If you want a conjecture without big-Oh notation for bounded-error quantum query complexity (or for that matter bounded-error randomized query complexity), this will be messy since the bound will have ...
Robin Kothari's user avatar
2 votes
Accepted

Complexity of Parallelogram Range Minimum Query

This can be reduced to rectangular RMQ in $O(n^2)$ time and space. Create a new array $H$ where $H[i][i+j] := G[i][j]$, padding entries $H[i][k]$ with $k < i$ or $k \ge i + n$ with $\infty$. Run $...
Whosyourjay's user avatar
2 votes
Accepted

Agnostic query learning for DFAs

As mentioned in the comments, if you allow some extra additive slack of $\varepsilon\in(0,1]$ (an input parameter) in the error guarantee, and relax the success probability from one to $1-\delta$ (...
Clement C.'s user avatar
  • 4,481
2 votes
Accepted

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)$?

Interestingly, a pretty good answer to my question was already given in Wiedemann's seminal paper on solving sparse linear systems. I am actually quite familiar with the paper, but I had totally ...
Geoffroy Couteau's user avatar
1 vote

What is really the difference between membership queries and "querying in i.i.d?

Learning from iid queries (i.e., "examples" -- these aren't generally called "queries") is generally harder than learning from membership queries. For example, DFAs are very hard ...
Aryeh's user avatar
  • 10.6k
1 vote
Accepted

Composition theorem for randomized communication complexity

My understanding is that it's not following from [Nisan94], but from [BCW98] (note that there are two citations provided from Theorem 5), specifically their Theorem 2.1. while phrased for quantum, ...
Clement C.'s user avatar
  • 4,481
1 vote

What is known about learning a maximal independent set in a (very) sparse graph?

Roughly $O(k \log(n/k))$ queries suffice, in the regime you are talking about. We can equivalently think of this as finding a minimal vertex cover for $G$, given ability to query whether a particular ...
D.W.'s user avatar
  • 12.2k
1 vote
Accepted

Randomized and deterministic query complexity of symmetric functions

Ok, I found the answer in this survey: http://homepages.cwi.nl/~rdewolf/publ/qc/dectree.pdf The sensitivity $s(f)$ of a (nonconstant) symmetric function $f$ is $s(f) \geq \lceil\frac{n+1}{2}\rceil$. ...
permanganate's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible