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

learn more… | top users | synonyms

4
votes
0answers
102 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 ...
6
votes
1answer
66 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
219 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
76 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
111 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 ...
15
votes
1answer
429 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 ...
5
votes
1answer
105 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
62 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
204 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
197 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
141 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
123 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 ...
4
votes
0answers
141 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 ...
5
votes
1answer
104 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
123 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
125 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 ...
9
votes
1answer
479 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
194 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
78 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
403 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
132 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
123 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
0answers
280 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
125 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 ...
3
votes
1answer
112 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
123 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
198 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
183 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
140 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
122 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
98 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
81 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
112 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
327 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
658 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
87 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
522 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
439 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 ...
5
votes
2answers
178 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
282 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 ...
3
votes
1answer
393 views

Ackermann Function Time Complexity

Are there any known problems that have an Ackermann function time complexity lower bound?
12
votes
0answers
198 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
116 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
181 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
89 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 ...
1
vote
1answer
60 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
308 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 ...
24
votes
3answers
2k 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, ...
19
votes
2answers
462 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 ...