Questions tagged [lower-bounds]

questions about lowerbounds on functions, usually the complexity of an algorithm or a problem

69 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
45
votes
0answers
1k views

Monotone complexity of s-t connectivity

In the problem CONN, we obtain a directed $n$-vertex graph (encoded as a boolean string of $n^2$ bits, one for each potential edge), and want to decide whether there is a path between all $n^2$ pairs $...
30
votes
0answers
4k 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\}$. (...
16
votes
0answers
443 views

Can short-distance connectivity be harder than connectivity?

Has anybody seen the following (or similar) question being considered: Can it be easier to determine the presence/absence of $s$-$t$ paths than to determine the presence/absence of short $s$-$t$ ...
15
votes
0answers
311 views

Set Intersection lower bounds

Consider $S_1, ...,S_n \subseteq [U]$ where size of $U$ is polylogarithmic in $n$. We allow infinite time to pre-process these sets and then ask queries of the form $S_i \cap S_j$ is empty or not. We ...
15
votes
0answers
579 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 ...
15
votes
1answer
394 views

Characterization of read-once formulae over the full binary basis

Background A read-once formula over a set of gates (also called a basis) is a formula in which each input variable appears once. Read-once formulas are commonly studied over the De Morgan basis (...
12
votes
0answers
227 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 ...
10
votes
0answers
264 views

Monotone circuit complexity of matroids?

Call a monotone boolean function $f$ a matroid function if its minterms are bases of some matroid. I am interested in monotone circuit complexity of such functions, even when we "tie hands" of these ...
10
votes
0answers
156 views

Hardness in P: methods to show optimality of $O(m^2n)$-like time?

In recent years, there has been exciting work in proving lower bounds for polynomial-time problems conditional on conjectures like SETH or "All-Pairs-Shortest-Paths (APSP) cannot be solved in $O(|V|^{...
10
votes
0answers
273 views

Lower bound method for ordered binary decision diagrams

This is an idea/question inspired by the question and answer of Boolean functions with exponential size OBDD representation in all orders except one order?: If you want to prove some exponential ...
9
votes
0answers
150 views

Fourth(?) moment method for minimum value

I would like to lower bound the quantity $\Pr[X\ge t, Y\ge t]=\Pr[\min(X,Y)\ge t]$ using the small moments of $X$, $Y$ and $XY$. In particular I am interested in the case where $E[X]=E[Y]=0$, but $E[X ...
9
votes
0answers
468 views

How to prove “obvious” facts?

The title is somewhat "arrogant": say, most of us treat $P\neq NP$ as an "obvious" fact, albeit no proof is in sight. But my question is at a much, much lower level, is about a fact which "should be" ...
9
votes
0answers
164 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 ...
8
votes
0answers
100 views

Reference for a circuit lower bound for slightly superexponential time

It is known that $EXP$ doesn't have circuits of size $n^k$. On the other hand proving $10 n$ lower bound on circuit size for $E$, $NE$ or even $E^{NP}$ is a known open problem. My question is ...
8
votes
0answers
266 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 ...
8
votes
0answers
256 views

Existence of “colouring matrices” — a generalisation

This is a generalisation of the following post: Existence of "colouring matrices". As the base case turned out to be fairly straightforward (in essence, precisely equal to the existence of Sperner ...
8
votes
0answers
249 views

For median is it optimal to compare in pairs first?

Median can be done in linear time and is now down to (I think) $2.97n$. The lower bounds is (I think) $(2+\epsilon)n$ where $\epsilon$ is very small. The following theorem, if true, may help improve ...
7
votes
0answers
290 views

Why is it so difficult to study Sum of Squares (SoS) algorithms with degree $d>4$?

In many publications on the computational complexity of Sum of Squares (SoS) algorithms, it is typical to study the degree-$4$ relaxation; e.g. Rounding Sum-of-Squares Relaxations Sum-of-Squares ...
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 ...
6
votes
0answers
139 views

Lower bound for Yao's algorithm on general addition chains?

An addition chain of size $n$ for given integers $n_1,n_2\dots ,n_p$ is a sequence of integers $k_1,k_2\dots ,k_n$ such that $k_1=1$, for all $i$ $(2\le i\le m)$ we have $k_i=k_j+k_m$ for some $1\le ...
6
votes
0answers
94 views

Lower bounds for randomized frequency estimation algorithms

Consider a stream of elements $s_1s_2\ldots s_N$. A counter-based frequency estimation algorithm uses $m$ counters and is required to answer queries of the form "How many times did $x$ appear"? It ...
6
votes
0answers
240 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, ...
6
votes
0answers
242 views

Data structures lower bounds on Turing machines

Have there been any results on lower bounds for implementing data structures on Turing machines, e.g. stacks, queues, etc ? I guess that people are mostly interested in models with random access, but ...
6
votes
0answers
202 views

Lowerbounds for in-situ permutation

What is the best known lowerbound for the worst case complexity of in-situ permutation (also called in-place rearrangement)? Has there been any reported progress after the 1970's article by Knuth (...
5
votes
0answers
108 views

Lower bound for enumerating k closest pair of points

Consider 1 dimensional points $x_1, \dots x_n, x_i \in \mathbb{R}$ where the distance between any two points is defined as $d(x_i, x_j) = \vert x_i - x_j \vert$. The goal is to enumerate all $n^2$ ...
5
votes
0answers
51 views

Inapproximability Results for APX-hard Geometric Optimization Problems

A lot of Geometric Optimization problems are NP-hard and APX-hard to approximate (No PTAS unless P=NP). One example of the geometric set cover problem can be found here. However, it is not easy to ...
5
votes
0answers
138 views

How hard is it to generate a set of relatively prime numbers between two given bounds?

Informal Question How hard is it to generate a set of relatively prime numbers between two given bounds? Decision Problem Given $a$, $b$, and $k \in \mathbb{N}$. Does there exist a set $S \...
5
votes
0answers
188 views

How hard is APPROXIMATE-#SAT?

It is well known that the problem of counting the satisfying assignments of SAT, namely the problem #SAT, is #P-complete. It is also suspected (somewhat less widely) that even deciding SAT should ...
5
votes
0answers
87 views

Using epsilon biased sets for circuit lower bounds

I have seen instances of how the technique of epsilon biased sets can be used to construct hard functions against a circuit class - like how in the recent paper of Kane-Williams this was used to ...
5
votes
0answers
159 views

Converse to natural proofs theorem?

Natural proofs paper shows 'if there is a natural property not possessed by any function in P/poly then there is no $2^{n^\epsilon}$-hard PRG'. Is it easy to see the converse 'if there is no $2^{n^\...
5
votes
0answers
207 views

What is the status of Determinantal Complexity of Permanent

Recently Landsberg and Ressayre announced an exponential lower bound for permanent's determinantal complexity assuming certain symmetry conditions. What is the status of the problem of Permanent's ...
5
votes
0answers
115 views

Tools to bound the singular values of a finite sum of random matrices from below?

Matrix Chernoff bounds (see also this arXiv paper) are usually used to give upper bounds on the largest eigenvalue of a finite sum of random matrices. Sometimes it can also be used to give a lower ...
5
votes
0answers
269 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 ...
4
votes
0answers
184 views

Is $NEXP^{NP}$ known to not be contained in $NP/poly$?

To the best of my knowledge, it is known that $NEXP^{NP} \nsubseteq P/poly$, but it's still not known if $NEXP \nsubseteq P/poly$. For more info, see "Superpolynomial circuits, almost sparse oracles ...
4
votes
0answers
91 views

Sampling Functions Efficiently vs Pseudorandom Generators

Let $X$ be a set of $n$-bit Boolean functions of the form $f:\{0,1\}^n\rightarrow \{0,1\}$. For instance, $X$ could be the set of $n$-bit monotone Boolean functions, or the set of $n$-bit functions ...
4
votes
0answers
217 views

Algebraic decision trees and adversary arguments

In the comparison tree model, we establish lower bounds on computing $\min$ and $\max$ of $n$ numbers via the adversary argument. Are there problems on which we know lower bounds in the algebraic ...
4
votes
0answers
126 views

Natural Problems NSPACE[n] but not in DTIME[n]

It is known that $\mathrm{DTIME}[n]\subseteq \mathrm{DSPACE}[n/\log n]$. Therefore, there are languages in $\mathrm{DSPACE}[n]$ which are not in $\mathrm{DTIME}[o(n\log n)]$. Are there examples of "...
4
votes
0answers
165 views

Nondeterministic communication complexity of Hamming distance

It is something that I think should be known: what is nondeterministic communication complexity of following task: is $H(x,y) \geq k$? There is an obvious upper bound $k \log(n)$. I would expect ...
4
votes
0answers
207 views

One-way randomized complexity of (variants of) Gap-Hamming-Distance?

The $\textsf{GapHammingDistance}$ problem over $\{0,1\}^n$ is defined as follows: Alice (resp. Bob) is given an input $x\in\{0,1\}^n$ (resp, $y\in\{0,1\}^n$), under the promise that their Hamming ...
3
votes
0answers
91 views

Why do most 0/1 matrices need linear arithmetic circuits of size $\Omega(n^2/\log(n))$?

I am reading Alon et al.'s paper Linear Circuits over $GF(2)$ and I am having trouble seeing the counting argument showing that most matrices need a circuit of size $\Omega(n^2/\log n)$. This result ...
3
votes
0answers
51 views

Lower bound for reversing a list using queues

How do you prove (or disprove) that a list of length $n$ cannot be reversed in time $o(n \log n)$ using $O(1)$ queues? Each queue is FIFO. Time refers to the number of operations on the queues. ...
3
votes
0answers
161 views

Circuit's with gate computing only “simple” functions

I was curious if something like that is known or was studied. Let's call a function simple if it is computable by $AC_0$ circuit of depth $\leq d$ and size $\leq n^k$ for fixed $k,d$. Now let's ...
3
votes
0answers
130 views

Finding median in a changing array

Consider the problem of needing to support an $n$ integers array structure with two operations: Set(k,v) - set the $k$'th integer to value $v$ (i.e. $A[k]=v$). Median() - return the median value of ...
3
votes
0answers
179 views

$CIS_G$ problem deterministic lower bound

In notes, http://www.cs.toronto.edu/~toni/Courses/CommComplexity2/Lectures/clique-notes.pdf, it is mentioned towards end of section $4$ that http://dl.acm.org/citation.cfm?id=237817 shows that ...
3
votes
0answers
105 views

What is the strongest known lower bound against SIZE(n)?

What is the best known lower bound against (nonuniform) circuits of size $O(n)$? I understand that we don't know of any explicit functions that need circuits of size more than something like $5n$. But ...
3
votes
0answers
169 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 ...
3
votes
0answers
353 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 ...
3
votes
0answers
457 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 ...
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 ...