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

learn more… | top users | synonyms

17
votes
0answers
334 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 ...
2
votes
0answers
52 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 ...
20
votes
1answer
356 views

best known 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
67 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
415 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 ...
3
votes
2answers
86 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
240 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
188 views

Ackermann Function Time Complexity

Are there any known problems that have an Ackermann function time complexity lower bound?
11
votes
0answers
94 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
85 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
156 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
82 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
52 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
257 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 ...
21
votes
3answers
1k 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, ...
18
votes
1answer
201 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 ...
0
votes
0answers
80 views

Does this meet the space requirements for the lower 3-SAT bounds?

According to "What are the best current lower bounds on 3SAT?", Ryan Williams has an answer that states that the (time * space) requirements for 3-SAT must meet or exceed $n^{2 \cos(\pi/7) - o(1)}$ ...
-1
votes
1answer
196 views

equivalent way(s) of expressing P=?NP problem in linear programming?

the paper "In defense of the Simplex Algorithm's worst-case behavior" Disser/Skutella [1] was recently cited on this tcs.se site by saeed on another interesting question. the paper introduces the idea ...
21
votes
2answers
1k views

Representing OR with polynomials

I know that trivially the OR function on $n$ variables $x_1,\ldots, x_n$ can be represented exactly by the polynomial $p(x_1,\ldots,x_n)$ as such: $p(x_1,\ldots,x_n) = 1-\prod_{i = ...
11
votes
0answers
123 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 ...
2
votes
0answers
86 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 ...
2
votes
1answer
172 views

Subset Sum bounds

Are there any bounds for the subset problem with respect to the number of the terms involved in the sum and the range of the possible values?For example looking for some 2 terms whose sum equals 3 you ...
18
votes
2answers
562 views

Bounds on the size of the smallest NFA for L_k-distinct

Consider the language $L_{k-distinct}$ consisting of all $k$-letter strings over $\Sigma$ such that no two letters are equal: $$ L_{k-distinct} :=\{w = \sigma_1\sigma_2...\sigma_k \mid \forall ...
9
votes
2answers
239 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 ...
3
votes
0answers
135 views

sketch of Razborovs 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 ...
7
votes
1answer
93 views

Lower bounds on alternative models of multiparty communication complexity

I'm a newcomer to communication complexity, and so far I've read the chapter in Arora-Barak and some papers giving lower bounds in various applications. A priori the definition of multiparty ...
3
votes
2answers
954 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 ...
4
votes
2answers
281 views

P/poly vs NP separation based on circuit trees instead of DAGs

there are various theorems that relate major complexity class separations to circuit family DAGs sizes, in particular for P/poly vs NP. in contrast, are there theorems/conjectures that relate ...
0
votes
1answer
51 views

Lower bounds on counting functions

I have a question about counting problems on arbitrary (not necessarily polynomial time) functions. Let $F_n = \{f : \{0,1\}^n \to \{0,1\}\}$ be the set of all boolean functions with $n$ inputs ...
5
votes
1answer
182 views

Lower bounds for formulae sizes for addition

I am interested in the conversion of $\sum_{i=1}^n x_i = y$ to 3-CNF. Here $x_i$ is a binary 0/1 variable and $y$ is some positive integer. There are a number of practical methods for doing this, ...
8
votes
4answers
434 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\}$, ...
7
votes
1answer
99 views

Is it known whether hypergraph minimal covers are P-enumerable?

Is it known or unknown whether hypergraph minimal covers are P-enumerable? I would be most happy with lower bounds. I'd also like to hear about conditional results, which assume some conjecture is ...
2
votes
0answers
129 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 ...
10
votes
2answers
234 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 ...
8
votes
0answers
180 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 ...
3
votes
0answers
199 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 ...
5
votes
0answers
218 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, ...
9
votes
2answers
243 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 ...
1
vote
1answer
209 views

“Send Once”-One way Multiparty Communication Complexity

There are plenty results on multiparty communication complexity, and one way protocol which anyone playing communicatin games is able to send one person, is a basic setting. I want to consider more ...
7
votes
0answers
131 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 ...
11
votes
2answers
419 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
2answers
506 views

Status on circuit lower bounds for polylog-bounded depth circuits

Bounded depth circuit complexity is one of the main areas of research within circuit complexity theory. This topic has origins in results like "the parity function is not in $AC^{0}$" and "the mod $p$ ...
19
votes
2answers
810 views

Lower bound for determinant and permanent

In light of the recent chasm at depth-3 result (which among other things yields a $2^{\sqrt{n}\log{n}}$ depth-3 arithmetic circuit for the $n \times n $ determinant over $\mathbb{C}$), I have the ...
8
votes
1answer
364 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 ...
3
votes
0answers
175 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
98 views

Correlation bounds

Is there any survey of results other than viola's on correlation bounds and its applications? Also is there any lecture notes on gowers uniformity and its applications in proving correlation bounds?
10
votes
1answer
627 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 ...
4
votes
1answer
288 views

Probabilistic circuit complexity or size of probabilistic 2-way automata for Boolean functions

If we consider circuits with arbitrary binary logic gates one can prove by a counting argument that there exists a Boolean function on $n$ variables that require a circuit of size $ \Theta \left( ...
4
votes
2answers
280 views

lower bound of majority function?

If a circuit ({AND OR NOT} circuit) with depth d computes the majority function, what's the best lower bound for majority function? I know the lower bound for parity function is $ 2^{\Omega (n^{1/d})} ...
24
votes
0answers
1k 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\}$. ...