Questions tagged [lower-bounds]

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

Filter by
Sorted by
Tagged with
14
votes
1answer
458 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 ...
14
votes
1answer
825 views

Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?

Question: Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines? Background: I recently stumbled upon the ...
14
votes
1answer
1k 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 ...
13
votes
2answers
445 views

Is it possible to use random restrictions to obtain a lower-bound for $\mathsf{TC^0}$?

There are several well-known $\mathsf{AC^0}$ circuit size lower-bound results based on random restrictions and the Switching Lemma. Can we develop a Switching Lemma result to prove a size lower-bound ...
13
votes
2answers
4k views

Simple proof of Ω(n lg n) worst-case bound for uniqueness/distinctness?

There are several proofs for the loglinear lower bound for the element uniqueness/distinctness problem (based on algebraic computation trees or adversarial arguments), but I'm looking for one that's ...
13
votes
1answer
302 views

Reference to lower bound on separator in a grid?

It is easy to verify that given the d dimensional grid of the integer points $\{1,\ldots,n\}^d$, with the regular adjacency, one can find a separator of size $n^{d-1}$ (just pick any middle hyperplane,...
12
votes
3answers
860 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 ...
12
votes
2answers
558 views

Which problems in computational geometry or graph theory are believed to be $\Omega(n^3)$?

This is intended as a follow up question to Robin Kothari's previous post on polynomial time hardness results. Specifically, I'm interested in seeing some hardness proofs for problems that are ...
12
votes
1answer
520 views

Problems to reduce from to prove an $\Omega(n\log n)$ lower bound

What are the standard problems we can reduce from to prove $\Omega(n\log n)$ lower bounds? Of course, state problems other than sorting and element distinctness.
12
votes
2answers
2k views

Reversing a list using two queues

This question is inspired by an existing question about whether a stack can be simulated using two queues in amortized $O(1)$ time per stack operation. The answer seems to be unknown. Here is a more ...
12
votes
1answer
532 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}\,, $$ ...
12
votes
1answer
769 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 ...
12
votes
2answers
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 ...
12
votes
1answer
477 views

Monotone circuit complexity of computing functions on sparse inputs

The weight $|x|$ of a binary string $x\in\{0,1\}^n$ is the number of ones in the string. What happens if we are interested in computing a monotone function on inputs with few ones? We know that ...
12
votes
1answer
553 views

Compressing information about the halting problem for oracle Turing machines

The halting problem is well-known to be uncomputable. However, it is possible to exponentially "compress" information about the halting problem, so that decompressing it is computable. More precisely,...
12
votes
0answers
270 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 ...
11
votes
1answer
986 views

What are the current best known upper and lower bounds on the (un)satisfiability threshold for random k-sat and/or 3-sat?

I would like to know the current state of the phase transition for random k-sat, given n variables and m clauses, what is the best known c=m/n for upper and lower bounds.
11
votes
2answers
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 ...
11
votes
1answer
577 views

Lower bounds for learning in the membership query and counterexample model

Dana Angluin (1987; pdf) defines a learning model with membership queries and theory queries (counterexamples to a proposed function). She shows that a regular language that is represented by a ...
11
votes
4answers
600 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\}$, ...
11
votes
2answers
469 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 ...
11
votes
1answer
463 views

Lower bounds for Nondeterministic Multiparty Communication

This is a continuation of my previous question on communication lower bounds for partial boolean functions. Can someone suggest any reference on lower bounds for nondeterministic multiparty ...
11
votes
1answer
648 views

Using Kolmogorov complexity to establish proof complexity lower bounds?

The motivation for this question is the fact that most n-bit strings are incompressible. Intuitively, we can propose by analogy that most proofs for Tautologies are incompressible to polynomial size. ...
10
votes
3answers
759 views

Maximum shortest word accepted by pushdown automata

Given a fixed alphabet, consider all deterministic pushdown automata with $n$ states that accept a nonempty language. What is the maximum length of the shortest word accepted by a deterministic ...
10
votes
1answer
481 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)$, ...
10
votes
2answers
427 views

Lower bounds for linear satisfiability problem

In SODA 1995, Jeff Erickson showed lower bounds for linear satisfiability (checking if a some $r$-subset of $n$ real numbers satisfies a linear equation on $r$ variables). The proof method uses ...
10
votes
1answer
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 ...
10
votes
2answers
609 views

What happens if we improve the time hierarchy theorems?

In a nutshell, the time hierarchy theorems say that a Turing machine can solve more problems if it has more time for computation. In detail for deterministic TM and time-constructable functions $f,g$ ...
10
votes
0answers
305 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
162 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
283 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
2answers
329 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 ...
9
votes
1answer
756 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 ...
9
votes
2answers
487 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 ...
9
votes
2answers
212 views

Existence of "colouring matrices"

Edit: there is now a follow-up question related to this post. Definitions Let $c$ and $k$ be integers. We use the notation $[i] = \{1,2,...,i\}$. A $c \times c$ matrix $M = (m_{i,j})$ is said to be ...
9
votes
2answers
849 views

Can three stacks be implemented in one array, with O(1) push/pop time?

Two stacks can be efficiently implemented using one fixed sized array: stack #1 starts from the left end and grows to the right, and stack #2 starts from the right end and grows to the left. Is the ...
9
votes
1answer
722 views

Lower bounds on the Threshold function

In decision tree complexity of a boolean function, a very well know lower bound method is to find a (approximate) polynomial that represents the function. Paturi gave a characterization for symmetric ...
9
votes
1answer
184 views

Separation of classes with different amounts of advice?

The time hierarchy theorem lets one show that, for example, there are problems in P that cannot be solved in time less than const*n^2 by a Turing machine. But give the Turing machine some advice and ...
9
votes
1answer
644 views

On optimality of Grover algorithm with high success probability

It is well-known that bounded error quantum query complexity of the function $OR(x_1,x_2,\ldots, x_n)$ is $\Theta(\sqrt{n})$. Now the question is what if we want our quantum algorithm to succeed for ...
9
votes
0answers
168 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
508 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
201 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
2answers
1k views

(0,1)-vector XOR problem

this is a rewrite of another recent question of mine [1] that wasnt stated well (it had a semi obvious simplification, mea culpa) but I think theres still a nontrivial question at the heart of it. ...
8
votes
1answer
1k views

How to generate a permutation uniformly by repeating using an one-bit uniform random generator?

If I have an one-bit uniform random generator, how can I use it to generate a permutation uniformly for the sequence {1, 2, ..., n}. I have a solution: run the one-bit random generator n*n times to ...
8
votes
3answers
794 views

One way randomised communication complexity of disjointness

I am looking for a reference for the (classical) one way randomised communication complexity of disjointness when the universe can be large. Say Alice and Bob both have sets of size $m$ chosen from a ...
8
votes
2answers
282 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
516 views

Conditional results implying difficulty of improving upper/lower bounds for permanent

Let $A$ be a given square matrix. Is there any evidence that beating quadratic lower bounds for $B$ such that $\text{det}(B) = \text{per}(A)$ could be hard? Is there any plausible conjecture which ...
8
votes
3answers
251 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 ...
8
votes
1answer
378 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 ...
8
votes
2answers
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 ...