Questions tagged [lower-bounds]
questions about lowerbounds on functions, usually the complexity of an algorithm or a problem
279
questions
1
vote
0
answers
87
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? ...
- 1,130
15
votes
1
answer
562
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)$...
- 6,685
5
votes
2
answers
514
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 ...
- 53
2
votes
1
answer
468
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 ...
- 63
5
votes
1
answer
1k
views
Ackermann Function Time Complexity
Are there any known problems that have an Ackermann function time complexity lower bound?
- 133
19
votes
0
answers
1k
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 ...
- 11.7k
9
votes
0
answers
215
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 ...
- 525
3
votes
1
answer
1k
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 ...
user22369
0
votes
0
answers
96
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{...
- 171
2
votes
1
answer
137
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 ...
- 2,121
8
votes
1
answer
400
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 ...
- 13.9k
25
votes
3
answers
4k
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-...
- 11.5k
21
votes
2
answers
914
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\}...
- 13.5k
0
votes
0
answers
136
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)}$ ...
- 2,100
1
vote
1
answer
618
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 ...
- 11k
17
votes
2
answers
782
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....
- 7,629
23
votes
3
answers
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\...
- 659
12
votes
0
answers
284
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 ...
- 1,085
2
votes
0
answers
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 ...
- 1,345
3
votes
1
answer
754
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 ...
- 173
18
votes
2
answers
830
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]...
- 9,438
11
votes
2
answers
5k
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 ...
- 18.9k
5
votes
0
answers
293
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 ...
- 11k
7
votes
1
answer
187
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 ...
- 1,318
8
votes
2
answers
8k
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 ...
- 181
4
votes
2
answers
545
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/...
- 11k
0
votes
1
answer
168
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 (...
- 617
5
votes
1
answer
226
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, ...
- 3,950
11
votes
4
answers
640
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\}$, ...
- 4,451
7
votes
1
answer
131
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 ...
- 4,796
3
votes
0
answers
217
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 ...
- 131
3
votes
0
answers
184
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 bounds ...
- 549
11
votes
2
answers
551
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 ...
- 4,001
8
votes
0
answers
305
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 ...
- 2,482
3
votes
0
answers
383
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 ...
- 549
6
votes
0
answers
272
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, ...
- 2,100
9
votes
2
answers
354
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 ...
- 5,531
2
votes
1
answer
322
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 ...
- 21
7
votes
0
answers
156
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 ...
- 171
13
votes
2
answers
2k
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 ...
- 341
18
votes
2
answers
1k
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$ ...
- 279
22
votes
2
answers
2k
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 ...
- 1,344
10
votes
1
answer
801
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 ...
- 103
3
votes
0
answers
659
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 ...
- 31
14
votes
1
answer
476
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 ...
- 763
2
votes
0
answers
117
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?
- 21
11
votes
1
answer
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
1
answer
502
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/...
- 171
6
votes
2
answers
1k
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})} ...
- 161
32
votes
0
answers
6k
views
Combinatorics of Bellman-Ford or how to make cyclic graphs acyclic?
Roughly speaking, my question is:
How costly is to make a cyclic graph
acyclic while preserving all simple $s$-$t$ paths?
Let $K_n$ be a complete undirected graph on vertices $\{0,1,\ldots,n+1\}$.
(...
- 6,685