Questions tagged [lower-bounds]

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

Filter by
Sorted by
Tagged with
4
votes
1answer
143 views

Hardness of Subgraph isomorphism problem for sparse pattern graph

Subgraph isomorphism problem is a well studied problem: given graphs $G$ and $H$, one needs to answer if $H$ contains $G$ as a subgraph. It was proven that this problem requires $|H|^{\theta(|G|)}$ ...
15
votes
0answers
313 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 ...
4
votes
0answers
92 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 ...
7
votes
1answer
270 views

How much memory is needed for counting distinct elements in a stream exactly with high probability

Assume we know a parameter $n\in\mathbb N$, and then get to observe a sequence of elements $x_1,\ldots, x_n$, one at a time. Our goal is to count the number of distinct elements in $x_1,\ldots, x_n$, ...
9
votes
1answer
311 views

Is the Kolmogorov complexity of the truth tables of the halting problem known asymptotically?

Let $HALT_n$ denote the string of length $2^n$ corresponding to the truth table of the halting problem for inputs of length $n$. If the sequence of Kolmogorov complexities $K(HALT_n)$ were $O(1)$, ...
4
votes
0answers
227 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
166 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 ...
3
votes
1answer
219 views

How can we bound the optimal solution of the dual bin packing when we solve the knapsack problem for each bin?

I have these two problems: Problem 1 (Dual bin packing problem) Instance: A set of $n$ items where each item $i$ has weight $w_i$. A set of $k$ bins where each bin has capacity $W$. Question: Find ...
6
votes
1answer
199 views

Two papers give contradictory bounds on linear probing. How do I resolve the disparity?

I've been reading over two papers recently. The first, "Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream" proves that, assuming there is sufficient entropy in a data source, ...
10
votes
0answers
267 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 ...
12
votes
1answer
486 views

Are arithmetic circuits weaker than boolean?

Let $A(f)$ denote the minimum size of a (non-monotone) arithmetic $(+,\times,-)$ circuit computing a given multilinear polynomial $$ f(x_1,\ldots,x_n)=\sum_{e\in E}c_e\prod_{i=1}^n x_i^{e_i}\,, $$ ...
8
votes
3answers
220 views

Showing that interval-sum queries on a binary array can not be done using linear space and constant time

You are given a $n$-sized binary array. I want to show that no algorithm can do the following (or to be surprised and find out that such algorithms exist after all): 1) Pre-process the input array ...
4
votes
1answer
492 views

Space complexity for multiplying $m$ matrices

Suppose you have $m$ $n$ by $n$ matrices $M_1,M_2,\dotsc,M_m$, and you want to calculate their product $\prod_{i=1}^{m} M_i$. The naive method use $m \cdot poly(n)$ times but needs $poly(n)$ memory. ...
0
votes
1answer
125 views

Lowerbound for the minimum distance between points in a “nice” triangulation

Suppose we have a unit square $S$ that contains $n$ points. Assume we always have a point at each of the four corners. No we triangulate $S$ by adding non-intersecting segments between the points. ...
3
votes
0answers
132 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 ...
7
votes
1answer
127 views

Lower bounds for noncommutative arithmetic circuits with exact division?

It is known that for general arithmetic circuits there is not much of a difference between standard model and one with division: any circuit with divisions that computes a polynomial can be simulated ...
14
votes
1answer
763 views

Monotone arithmetic circuit complexity of elementary symmetric polynomials?

The $k$-th elementary symmetric polynomial $S_k^n(x_1,\ldots,x_n)$ is the sum of all $\binom{n}{k}$ products of $k$ distinct variables. I am interested in the monotone arithmetic $(+,\times)$ circuit ...
0
votes
2answers
134 views

Mergeable Exact Order Statistics Data Structure

Given $n$ sets of integers $S_1, S_2, \cdots, S_n$, it is guaranteed that $$ x < y, \text{ for } \forall x \in S_i \text{ and } \forall y \in S_{i+1} $$ and let's denote this relationship as $S_i &...
10
votes
0answers
157 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|^{...
15
votes
1answer
597 views

Is Dynamic Programming never weaker than Greedy?

In the circuit complexity, we have separations between powers of various circuit models. In the proof complexity, we have separations between powers of various proof systems. But in the algorithmic,...
5
votes
1answer
169 views

Implications of a recent negative result to geometric complexity

A paper was posted in arxiv http://arxiv.org/pdf/1512.03798.pdf titled 'Rectangular Kronecker coefficients and plethysms in geometric complexity theory' by Christian Ikenmeyer and Greta Panova with ...
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 ...
8
votes
2answers
263 views

Uncertainties in GCT program

In https://en.wikipedia.org/wiki/Geometric_complexity_theory it is mentioned that ".. Ketan Mulmuley believes the program, if viable, is likely to take about 100 years before it can settle the P vs. ...
8
votes
1answer
346 views

Are there more polynomial time problems with complexity lower bounds?

I'm looking for more problems in $P$ with classical time complexity lower bounds. Some people might wonder how you could prove such a lower bound. See below. Exponential Lower Bounds: Claim: If ...
0
votes
1answer
160 views

What do these lower bounds really mean?

I was reading an abstract for a paper that gives a minimum number M of good agents that guarantees f-Byzantine gathering, if there are f Byzantine agents. It gives a lower bound of f+1 for strongly ...
7
votes
0answers
293 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 ...
4
votes
0answers
210 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 ...
6
votes
1answer
132 views

Lower bounds for nonuniform circuits and oracles separating complexity classes

I have read that Furst, Sax, and Sipser came up with their lower bound for nonuniform AC0 while trying to prove an oracle separation. Can someone explain how proving lower bounds for circuits and ...
9
votes
2answers
427 views

What's the “smallest” complexity class for which an $\omega \hspace{.02 in}(n)$ circuit lower bound is known?

I believe the answers to this question give classes such that for all polynomials $p$, there is a problem in the class which does not have circuits of size $p(n)$. However, I'm asking about circuit ...
5
votes
0answers
209 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 ...
14
votes
2answers
654 views

How many negations do we need to compute monotone functions?

Razborov proved that the monotone function matching is not in mP. But can we compute matching using a polynomial size circuit with a few negations? Is there a P/poly circuit with $O(n^\epsilon)$ ...
12
votes
1answer
523 views

L/P/PSpace vs P/NP

in 1979 Hopcroft/ Ullman wrote that L ⊆ P ⊆ NP ⊆ PSpace is known but L ⊊ PSpace is the only proper (& trivial) containment known although all are conjectured to be proper containments, and "where ...
3
votes
1answer
120 views

Symbolic Execution of the Quine-McCluskey Algorithim

If I understand correctly, the Quine–McCluskey algorithm will find the minimum boolean formula size for given boolean function. Has there been any attempts to (for lack of a better term) symbolically ...
19
votes
1answer
588 views

How to prove that USTCONN requires logarithmic space?

USTCONN is the problem that requires deciding whether there is a path from the source vertex $s$ to the target vertex $t$ in a graph $G$, where these are all given as part of the input. Omer Reingold ...
8
votes
2answers
260 views

New Space Lower-Bound Techniques for Streaming Algorithms

Is communication complexity (CC) the only known approach for streaming algorithms lower bounds? Are there any other techniques, even if conditional lower bounds? In general, are we satisfied with the ...
2
votes
1answer
218 views

Lower bound for finding repeated elements in sorted array

This is inspired by [1] (which still needs answers). What is the tight lower bound (or optimal algorithms) for the "finding repeated elements" problem: Given a sorted integer array of size $n$, how ...
16
votes
0answers
444 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$ ...
4
votes
1answer
172 views

Communication complexity of Independent Set game?

Consider the following communication game. Independent Set game Let $[n] = \{0,1,\dots,n-1\}$ and let $r$ be a positive integer smaller than $n/(1+\log n)$. Alice receives a set $X$ of edges, each ...
5
votes
1answer
363 views

Lower bounds for inversion counting in comparison model?

For counting the number of inversions in an array, there are many $O(n \log n)$ algorithms, e.g. the one that modifies Merge Sort. There is an easy $\Omega(n)$ lower bound simply because you have to ...
-3
votes
1answer
417 views

Using Yao's minimax principle [closed]

Consider the basic problem in which the input is an array A of n bits, and we need to output some index i with A[i]=1 (we can read a single bit each time). Can you give me an example using Yao's ...
2
votes
1answer
232 views

Is it possible to prove stronger bounds for the deterministic communication complexity compared to nondeterministic communication complexity?

Inspired by the questions Nondeterministic communication complexity of set disjointness?, I was wondering about the following: Is there an example of a function $f$ where the nondeterministic ...
6
votes
1answer
399 views

Nondeterministic communication complexity of set disjointness?

In the two-party setting, bounds of $\Theta(n)$ bits are known for deterministic and bounded-error randomized protocols for $\text{DISJ}_n$. (Here $\text{DISJ}_n$ is the $n$-element set disjointness ...
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 ...
1
vote
0answers
135 views

Consequences of the existence of the following algorithm: does it imply any complexity class separation / collapse?

Let $G$ be a $3$-regular graph. Let $O$ be the number of vertex covers of $G$ having odd cardinality, and let $E$ be the number of vertex covers of $G$ having even cardinality. Let $\Delta = O - E$. ...
5
votes
0answers
116 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 ...
3
votes
1answer
104 views

Lower bounds and impossibility results for distributed transactions

I am studying on distributed transactions, mainly on the correctness criteria (e.g., serializability (SR) and snapshot isolation (SI) in replicated settings) and their implementations. To avoid ...
3
votes
1answer
133 views

Number of different longest common substrings

Given an alphabet $\Sigma$ of size $k$ and two strings $w_1,w_2\in \Sigma^n$ of length $n$. The longest common substring problem asks for a longest string in the set $A(w_1,w_2)$ of all common ...
12
votes
3answers
600 views

Properties expressible in 2-CNF or 2-SAT

How does one show that a certain property cannot be expressed in 2-CNF (2-SAT)? Are there any games, such as pebble games? It seems that the classical black pebble game and the black-white pebble ...
23
votes
1answer
847 views

Why is HAMILTONIAN CYCLE so different from PERMANENT?

A polynomial $f(x_1,\ldots,x_n)$ is a monotone projection of a polynomial $g(y_1,\ldots,y_m)$ if $m$ = poly$(n)$, and there is an assignment $\pi:\{y_1,\ldots,y_m\}\to\{x_1,\ldots,x_n, 0,1\}$ such ...