Questions tagged [lower-bounds]
questions about lowerbounds on functions, usually the complexity of an algorithm or a problem
230
questions
22
votes
2answers
791 views
Best current space lower bound for SAT?
Following on from a previous question,
what are the best current space lower bounds for SAT?
With a space lower bound I here mean the number of worktape cells used by a Turing machine which uses a ...
1
vote
0answers
82 views
Implication of lower bounds in Boolean circuit to other models of computation
Suppose that one can prove that some hard function $f$ with $n$ bit input does not admit any Boolean circuit of size at most $n^t$.
Then, how strong can we say about how hard $f$ is in other models? ...
15
votes
1answer
495 views
Any polynomial which is hard to count but easy to decide?
Every monotone arithmetic circuit, i.e. a $\{+,\times\}$-circuit, computes some multivariate
polynomial $F(x_1,\ldots,x_n)$ with nonnegative integer coefficients. Given a polynomial
$f(x_1,\ldots,x_n)$...
5
votes
2answers
394 views
Lower bound proof for compressive sensing (Gel'fand widths)?
Let $x \in \mathbb{R}^n$ have $k$ non-zero entries. The main insight of compressive sensing is that there exist $m\times n$ matrices $A$ with $m = O(k \log n/k)$ such that any $x$ can be recovered ...
2
votes
1answer
358 views
Complexity lower bound of finding the factorial of a number
I was wondering about the complexity of the factorial of a number mostly because this problem is not referenced in the complexity books I have read.
Two similar problems, Matrix Multiplication and ...
5
votes
1answer
990 views
Ackermann Function Time Complexity
Are there any known problems that have an Ackermann function time complexity lower bound?
16
votes
0answers
605 views
Lower bounds on single-source shortest paths in directed graphs
Are there any non-trivial lower bounds on the complexity of single-source shortest paths (SSSP) in a directed graph, where all edges have non-negative edge weights? Can we rule out the possibility of ...
9
votes
0answers
173 views
References for de-amortization
I've been interested in looking into the area of de-amortization recently (i.e. finding data structures with matching worst-case and amortized running time bounds, or exhibiting lower bounds against ...
2
votes
1answer
407 views
Time complexity of d-dimensional convex hull
Consider the convex hull problem in $\Re^d$:
Input: a list of $n$ points $S$ in $\Re^d$,
Output: the vertices of the convex hull of $S$.
What is the best lower bound on the time complexity of ...
0
votes
0answers
94 views
To find OR of $\sqrt{n}$ numbers each of $n$ bits?
Given $\sqrt{n}$ numbers of $n$ bits each. I need to find its OR and store it at another number RESULT of $n$ bits.
Trivially it can be done in $\mathcal{O}(n \sqrt{n})$ time, or $\mathcal{O}(n \sqrt{...
2
votes
1answer
95 views
Lower bounds on simple hash table operations?
There are a variety of hash tables that support worst-case O(1)-time lookups and deletions and expected O(1)-time lookups. Is there a known lower-bound on hashing that says that there cannot be a hash ...
8
votes
1answer
357 views
Lower bound for NFA accepting 3 letter language
Related to a recent question (Bounds on the size of the smallest NFA for L_k-distinct) Noam Nisan asked for a method to give a better lower bound for the size of an NFA than what we get from ...
25
votes
3answers
3k views
Nontrivial algorithm for computing a sliding window median
I need to calculate the running median:
Input: $n$, $k$, vector $(x_1, x_2, \dotsc, x_n)$.
Output: vector $(y_1, y_2, \dotsc, y_{n-k+1})$, where $y_i$ is the median of $(x_i, x_{i+1}, \dotsc, x_{i+k-...
19
votes
2answers
712 views
Deterministic communication complexity vs partition number
Background:
Consider the usual two-party model of communication complexity where Alice and Bob are given $n$-bit strings $x$ and $y$ and have to compute some Boolean function $f(x,y)$, where $f:\{0,1\...
0
votes
0answers
125 views
Does this meet the space requirements for the lower 3-SAT bounds?
According to "What are the best current lower bounds on 3SAT?", Ryan Williams has an answer that states that the (time * space) requirements for 3-SAT must meet or exceed $n^{2 \cos(\pi/7) - o(1)}$ ...
1
vote
1answer
475 views
equivalent way(s) of expressing P=?NP problem in linear programming?
the paper "In defense of the Simplex Algorithm's worst-case behavior" Disser/Skutella [1] was recently cited on this tcs.se site by saeed on another interesting question. the paper introduces the idea ...
17
votes
2answers
598 views
Better lower bounds than 3n for non-boolean functions?
Blum's $3n-o(n)$ lower bound is the best known circuit lower bound over the complete basis for an explicit function $f : \{0,1\}^n \to \{0,1\}$, cf. Jukna's answer to this question for related results....
23
votes
3answers
1k views
Representing OR with polynomials
I know that trivially the OR function on $n$ variables $x_1,\ldots, x_n$ can be represented exactly by the polynomial $p(x_1,\ldots,x_n)$ as such:
$p(x_1,\ldots,x_n) = 1-\prod_{i = 1}^n\left(1-x_i\...
12
votes
0answers
233 views
Hardness of optimal sorting
For comparison-based sorting algorithms, asymptotically optimal algorithms in worst-case $\Theta(n\log n)$ comparisons are well known.
From a purely theoretical perspective, however,
exactly optimal ...
2
votes
0answers
96 views
Is this question $NP_R$ hard?
Consider $n$ variables $x_1, \cdots, x_n$ and
$f=\sum a_i x_1^{d_{i1}}\cdots x_n^{d_{in}}$ such that for each $i$, $d_{i1}+\cdots+d_{in}=d$ for some fixed $d$ and $a_i\geq 0$.
I am interested in the ...
2
votes
1answer
576 views
Subset Sum bounds
Are there any bounds for the subset problem with respect to the number of the terms involved in the sum and the range of the possible values?For example looking for some 2 terms whose sum equals 3 you ...
18
votes
2answers
713 views
Bounds on the size of the smallest NFA for L_k-distinct
Consider the language $L_{k-distinct}$ consisting of all $k$-letter strings over $\Sigma$ such that no two letters are equal:
$$
L_{k-distinct} :=\{w = \sigma_1\sigma_2...\sigma_k \mid \forall i\in[k]...
10
votes
2answers
4k views
2DFA that requires many states in equivalent DFA?
Is there a 2DFA with $n$ states (where $n$ is nontrivial, say at least 4) that requires at least $2^n$ states to simulate using any DFA?
A two-way DFA (2DFA) is a deterministic finite-state automaton ...
5
votes
0answers
270 views
Sketch of Razborov's paper “On the method of approximations”
(The following question has bothered me for many years.) Razborov seems to have obtained some of the strongest/award winning lower bounds on circuits found in the field over many years, largely ...
7
votes
1answer
175 views
Lower bounds on alternative models of multiparty communication complexity
I'm a newcomer to communication complexity, and so far I've read the chapter in Arora-Barak and some papers giving lower bounds in various applications.
A priori the definition of multiparty ...
6
votes
2answers
7k views
Top-k frequent items in data stream
Paper "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm" introduce an efficient algorithm which can help to estimate distinct items in large data set.
I am thinking about ...
4
votes
2answers
447 views
P/poly vs NP separation based on circuit trees instead of DAGs
there are various theorems that relate major complexity class separations to circuit family DAGs sizes, in particular for P/poly vs NP. in contrast,
are there theorems/conjectures that relate P/...
0
votes
1answer
74 views
Lower bounds on counting functions
I have a question about counting problems on arbitrary (not necessarily polynomial time) functions.
Let $F_n = \{f : \{0,1\}^n \to \{0,1\}\}$ be the set of all boolean functions with $n$ inputs (...
5
votes
1answer
208 views
Lower bounds for formulae sizes for addition
I am interested in the conversion of $\sum_{i=1}^n x_i = y$ to 3-CNF. Here $x_i$ is a binary 0/1 variable and $y$ is some positive integer. There are a number of practical methods for doing this, ...
11
votes
4answers
540 views
Lower bound for testing closeness in $L_2$ norm?
I was wondering if there was any lower bound (in terms of sample complexity) known for the following problem:
Given sample oracle access to two unknown distributions $D_1$, $D_2$ on $\{1,\dots,n\}$, ...
7
votes
1answer
120 views
Is it known whether hypergraph minimal covers are P-enumerable?
Is it known or unknown whether hypergraph minimal covers are P-enumerable? I would be most happy with lower bounds. I'd also like to hear about conditional results, which assume some conjecture is ...
3
votes
0answers
173 views
Proving greedy algorithm is optimal for a scheduling problem
First, the problem discription:
For a sequence of $4n$ tasks, $a_1a_2\dots a_{4n}$, where $a_i\in\{0,1\}\forall i$, put them sequentially to the tail of one of the two initially empty queues of ...
3
votes
0answers
175 views
Natural Proofs and methods for polylog depth circuit lower bounds
I have a question about the following question and its answer.
Status on circuit lower bounds for polylog-bounded depth circuits
In the above question, it is asked about methods to prove lower ...
11
votes
2answers
363 views
Is there an explanation for the difficulty of proving quadratic lower bounds for interesting NP problems?
This is a follow up to my previous question:
Best known deterministic time complexity lower bound for a natural problem in NP
I find it bewildering that we haven't been able to prove any quadratic ...
8
votes
0answers
274 views
Grigoriev-Karpinski for the permanent
Grigoriev and Karpinski (ps.Z) showed that any depth-3 circuit over a fixed finite field computing $\mathrm{Det}_n$ requires $2^{\Omega(n)}$ size. I had the misconception(?) until recently that the ...
3
votes
0answers
356 views
Streaming Algorithm Lower Bounds by Communication Complexity
I am learning the methods for proving lower bounds on streaming algorithms using communication complexity.
My question is about a basic technique to prove lower bounds on streaming models using the ...
6
votes
0answers
242 views
The latest concerning Valiant-Vazirani
I'm wondering what the best method obtained for the Valiant-Vazirani theorem is. We can state the following criteria:
(1) First and foremost, has anyone been able to derandomize it?
(2) If not, ...
9
votes
2answers
301 views
Lower bound on number of oracle calls for solving $n$ instances of the halting problem
I encountered the following question, which is an easy exercise (spoiler below).
We are given $n$ instances of the halting problem (i.e. TMs $M_1,...,M_n$), and we need to decide exactly which of ...
1
vote
1answer
304 views
“Send Once”-One way Multiparty Communication Complexity
There are plenty results on multiparty communication complexity, and one way protocol which anyone playing communicatin games is able to send one person, is a basic setting.
I want to consider more ...
7
votes
0answers
150 views
Size complexity of probabilistic two-way automata for a Boolean function
I'm interested in computing Boolean functions $f:\{0,1\}^n\rightarrow\{0,1\}$ with two-way finite automata and I will measure the complexity of a Boolean function by the number of states for the ...
12
votes
2answers
1k views
What's the most efficient algorithm for Divisibility?
What is the most efficient (in time complexity) algorithm known nowadays for the Divisibity Decision Problem: given two integers, say $a$ and $b$, does $a$ divide $b$? Let it be clear that what I ask ...
17
votes
2answers
790 views
Status on circuit lower bounds for polylog-bounded depth circuits
Bounded depth circuit complexity is one of the main areas of research within circuit complexity theory. This topic has origins in results like "the parity function is not in $AC^{0}$" and "the mod $p$ ...
22
votes
2answers
1k views
Lower bound for determinant and permanent
In light of the recent chasm at depth-3 result (which among other things yields a $2^{\sqrt{n}\log{n}}$ depth-3 arithmetic circuit for the $n \times n $ determinant over $\mathbb{C}$), I have the ...
9
votes
1answer
645 views
Can we get a sorted list from a sorted matrix in $O(n^2)$
I'm confused. I want to prove that that the problem of sorting a $n$ by $n$ matrix i.e. the rows and columns are in ascending order is $\Omega(n^2\log n)$.
I proceed by assuming that it can be done ...
3
votes
0answers
468 views
Is there a tight lower bound on the complexity of SSSP on a graph?
I'm an undergrad and I'm not sure if this is the right way to ask this question. I want to know the lower bound on single-source shortest path computation in a general graph. The graph is allowed to ...
14
votes
1answer
406 views
Best communication complexity lower bound of disjointness
It is well known that no deterministic two-party protocol can solve disjointness problem (DISJ) on $n$-bit inputs without sending $n+1$ bits in the worst case (see, e.g., the book by Kushilevitz and ...
2
votes
0answers
111 views
Correlation bounds
Is there any survey of results other than viola's on correlation bounds and its applications?
Also is there any lecture notes on gowers uniformity and its applications in proving correlation bounds?
10
votes
1answer
1k views
How many disjoint edge-cuts a DAG must have?
The following question is related to the optimality of the Bellman-Ford $s$-$t$ shortest
path dynamic programming algorithm (see this post for a connection). Also, a positive answer would imply that ...
4
votes
1answer
422 views
Probabilistic circuit complexity or size of probabilistic 2-way automata for Boolean functions
If we consider circuits with arbitrary binary logic gates one can prove by a counting argument that there exists a Boolean function on $n$ variables that require a circuit of size $ \Theta \left( 2^n/...
5
votes
2answers
731 views
lower bound of majority function?
If a circuit ({AND OR NOT} circuit) with depth d computes the majority function, what's the best lower bound for majority function?
I know the lower bound for parity function is $ 2^{\Omega (n^{1/d})} ...
