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

learn more… | top users | synonyms

4
votes
0answers
118 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 ...
1
vote
1answer
89 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
157 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, ...
9
votes
0answers
174 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 ...
13
votes
1answer
396 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
192 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 ...
5
votes
1answer
166 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
51 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. ...
4
votes
0answers
114 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 ...
8
votes
1answer
85 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
250 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
92 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
116 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
459 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,...
4
votes
1answer
120 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 ...
5
votes
0answers
69 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
216 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. ...
7
votes
1answer
215 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
147 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 ...
3
votes
0answers
126 views

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

In many literatures on the computational complexity of Sum of Square (SoS) algorithms, it is typical to study the degree-$4$ relaxation; e.g. Rounding Sum-of-Squares Relaxations (https://www.cs....
4
votes
0answers
152 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
111 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 ...
2
votes
0answers
129 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 ...
4
votes
0answers
143 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
587 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)$ ...
11
votes
1answer
228 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
83 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
430 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
178 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 ...
1
vote
1answer
144 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$, ...
15
votes
1answer
364 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
132 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 ...
4
votes
1answer
123 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
141 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
214 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
197 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
142 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
126 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
101 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 ...
2
votes
1answer
86 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
113 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 ...
9
votes
3answers
345 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 ...
22
votes
1answer
684 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 ...
3
votes
0answers
92 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 ...
22
votes
2answers
542 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 ...
1
vote
0answers
75 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
445 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
202 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
303 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 ...
4
votes
1answer
481 views

Ackermann Function Time Complexity

Are there any known problems that have an Ackermann function time complexity lower bound?