complexity lowerbounds
-1
votes
0answers
30 views
Time complexity in Big O notation for Harmonic series with first k terms missing [migrated]
Firstly, let's suppose there exists an algorithm where i iterates from 1 to n, spending n^2/i time in each iteration.
Thanks to the well known O(logn) upper bound for the Harmonic series, the big O ...
-2
votes
0answers
47 views
Finding the lower bounds of an algorithm [closed]
I am struggling to calculate the lower bounds of an algorithm. What is the right way to proceed.
For eg, I have the following algorithm
...
8
votes
0answers
128 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
124 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
198 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
207 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 ...
0
votes
1answer
141 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 ...
6
votes
0answers
98 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 ...
9
votes
0answers
146 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 ...
9
votes
2answers
315 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$ ...
18
votes
2answers
521 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
229 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 ...
1
vote
0answers
77 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 ...
1
vote
0answers
86 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
382 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
199 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
201 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})} ...
21
votes
0answers
546 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\}$.
...
6
votes
1answer
110 views
Lower bounds for 3SUM with a free cache
Consider the 3SUM problem: given a set $S$ of $n$ numbers identify $x$,$y$,$z$, s.t $x + y = z$. It is believed that the simple $O(n^2)$ algorithm is the best possible; reductions from 3SUM have been ...
7
votes
0answers
196 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 ...
1
vote
0answers
33 views
Lower bounds for minimum variance estimators in limited space
Cramer-Rao, Rao-Blackwell and Lehmann-Scheffé, all give you ways to prove that a statistical estimator has the lowest variance possible. Is there any CS related work on the minimum variance ...
6
votes
0answers
122 views
Data structures lower bounds on Turing machines
Have there been any results on lower bounds for implementing data structures on Turing machines, e.g. stacks, queues, etc ?
I guess that people are mostly interested in models with random access, but ...
32
votes
0answers
512 views
Monotone complexity of s-t connectivity
In the problem CONN, we obtain a directed $n$-vertex graph (encoded as a boolean string of $n^2$ bits, one for each potential edge), and want to decide
whether there is a path between all $n^2$ pairs ...
13
votes
1answer
278 views
Characterization of read-once formulae over the full binary basis
Background
A read-once formula over a set of gates (also called a basis) is a formula in which each input variable appears once. Read-once formulas are commonly studied over the De Morgan basis ...
17
votes
1answer
663 views
Can addition be carried out in less than depth 5?
Using carry look ahead algorithm we can compute addition using a polynomial size depth 5 (or 4?) $AC^0$ circuit family. Is it possible to reduce the depth? Can we compute the addition of two binary ...
2
votes
1answer
152 views
Exponential blowup in Simple Proof of a theorem of Statman by Mairson
I'm studying "A simple proof of a theorem of Statman" by H.G. Mairson.
At page 4, he encodes set/type theory in lambda calculus.
In particular, note che "op" trick in the definition of $eq_{k+1}$.
...
11
votes
1answer
204 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 ...
-2
votes
1answer
134 views
Lower bounds on $Q_{\epsilon}(IP)$
I want to show that $Q_{\epsilon}(IP) \geq (1-O(\epsilon))n$, where $IP:\{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$ is the usual mod 2 inner product.
I have Nayak's lower bound, but I am not sure ...
6
votes
1answer
284 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 ...
4
votes
0answers
202 views
Lower Bounds on Running time of Graph Algorithms
Are there any non-trivial lower bounds on the running time of graph algorithms in RAM/PRAM/
models of computation ? I am not looking for the NP-Hardness results here.
Following is a result that I ...
7
votes
0answers
239 views
Existence of “colouring matrices” — a generalisation
This is a generalisation of the following post: Existence of "colouring matrices".
As the base case turned out to be fairly straightforward (in essence, precisely equal to the existence of Sperner ...
8
votes
2answers
163 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 ...
5
votes
1answer
306 views
Razborov's Approximation methods
The approximation mothods is used for deriving lower bounds on the monotone circuit size of k-cliue and perfect matching problem.
People in parameterized complexity theory strongly believe that ...
0
votes
1answer
126 views
Functions and Counting Problems in Streaming Computation
I have read a stream computation paper in STOC07(Paul Beame, T. S. Jayram, and Atri Rudra. Lower bounds for randomized read/write stream algorithms.) and FOCS08（Paul Beame and Trinh Huynh. On the ...
8
votes
1answer
187 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 ...
2
votes
1answer
73 views
Lower bounds on batched query search
I am not much in the field of databases. But the problem I m facing is the following: given a database $D$, we receive a batch of distinct queries $Q = \{q_1, ..., q _k\}$, where each $q_i$ is a ...
2
votes
1answer
229 views
Questions about computing matrix rigidity
Matrix rigidity was introduced by Valiant in 1977:
The rigidity $Rig_M(r)$ of boolean matrix $M$ over GF(2) is the
smallest number of entries of $M$ that must be changed in order to
reduce ...
6
votes
2answers
381 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. ...
10
votes
0answers
282 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 ...
0
votes
0answers
97 views
covering an NxN grid using overlapping vs. non-overlapping windows residing k points in each
Let the problem, $P_{overlapping}$, be the following.
We have an $N_1 \times N_2$ grid. Each cell of the grid can have the
value either 0 or 1. Assume that we have $a \times b$ overlapping windows as
...
14
votes
2answers
450 views
Number of binary gates needed to compute AND and OR of n input bits simultaneously
What is the minimal number of binary gates needed to compute AND and OR of $n$ input bits simultaneously?
The trivial upper bound is $2n-2$. I believe that this is optimal, but how to prove this? The ...
9
votes
1answer
286 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.
20
votes
5answers
343 views
Reducing space usage of st-connectivity with multiple passes?
Suppose a graph $G$ with $n$ vertices is presented as a stream of $m$ edges, but multiple passes are allowed over the stream.
Monika Rauch Henzinger, Prabhakar Raghavan, and Sridar
Rajagopalan ...
12
votes
3answers
501 views
How can I show a Gap-P problem is outside #P
There are a number of problems in combinatorial representation theory and algebraic geometry for which no positive formula is known. There are several examples I am thinking of, but let me take ...
22
votes
2answers
934 views
Are the problems PRIMES, FACTORING known to be P-hard?
Let PRIMES (a.k.a. primality testing) be the problem:
Given a natural number $n$, is $n$ a prime number?
Let FACTORING be the problem:
Given natural numbers $n$, $m$ with $1 \leq m \leq ...
17
votes
1answer
569 views
Most efficient way to convert an $\text{AC}^0$ circuit to a circuit (of any depth) with gate fanout 1
EDIT (Aug 22, 2011):
I am further simplifying the question and putting a bounty on the question. Perhaps this simpler question will have an easy answer. I'm also going to strikethrough all the parts ...
21
votes
2answers
741 views
Formula size lower bounds for AC0 functions
Question:
What is the best known formula size lower bound for an explicit function in AC0? Is there an explicit function with an $\Omega(n^2)$ lower bound?
Background:
Like most lower bounds, ...
6
votes
0answers
136 views
Lowerbounds for in-situ permutation
What is the best known lowerbound for the worst case complexity of in-situ permutation (also called in-place rearrangement)? Has there been any reported progress after the 1970's article by Knuth ...
1
vote
0answers
168 views
Circuit lower bound for NAND based arbitrary deterministic computation [closed]
What is the lowest known lower-bound on the number of NAND gates needed in order to perform an arbitrary deterministic computation with a fixed length input and output?
10
votes
1answer
290 views
Progress on generalized star-height problem?
The (generalized) star height of a language is the minimum nesting of Kleene stars required to represent the language by an extended regular expression. Recall that an extended regular expression over ...
