Questions tagged [lower-bounds]
questions about lowerbounds on functions, usually the complexity of an algorithm or a problem
294 questions
4
votes
1
answer
186
views
Maintaining dynamic set of intervals and detect when two intervals intersect
Let $n$ be an integer. An interval is a range $[i,j]$ with $1 \leq i \leq j \leq n$, containing the list of all integers between $i$ and $j$ (endpoints included). I want a data structure $S$ that ...
- 11.6k
1
vote
0
answers
227
views
CET(n) >> BB(n)?
Catch-Em-Turing, CET(n), my invention.
We define a Catch-Em-Turing game/computational model with n agents placed on an infinite bidirectional ribbon, initially filled with 0.
Initialization:
The ...
- 11
1
vote
0
answers
143
views
What is the smallest algebraic circuit to compute product of a vector by a fixed square matrix?
Given a fixed $n \times n $ square matrix $M$ over a field of size $ \Omega(n^2) $.
What is the size $s_M$ of the smallest circuit that computes the function $f(x)= Mx$ ?
What is the largest $s_M$ ...
- 358
2
votes
1
answer
196
views
Lower-bound for size of set of vertices in a DAG Markov chain
Setting
I have a finite Markov chain $M$ where the underlying directed graph is a DAG (directed acyclic graph). Every vertex has two outgoing edges, each with probability $\frac{1}{2}$ (both of which ...
- 151
2
votes
0
answers
132
views
Matrix Vector Multiplication Bit Operations
$M\in\mathbb Z_{\geq0}^{m\times n}$ and $v\in\mathbb Z_{\geq0}^n$ where $\max_{i,j}M_{i,j}<2^t$ and $\max_iv_i<2^t$ holds.
If $M$ is not fixed it takes $mnt+nt$ bit operations to read the binary ...
- 13.8k
2
votes
0
answers
64
views
A better definition of "the comparison model"
In the comparison model we deal with lists of elements from an infinite linear order which can only be compared and are otherwise atomic. (Moreover, list operations should commute with permutations of ...
- 1,001
8
votes
0
answers
319
views
Enumerating $k$-Cliques with better than $O(n^k)$ preprocessing
Let us define the problem $k$-Clique enumeration as follows:
Input: A Graph $G$ with $n$ nodes.
Output: A data structure $D$ which can enumerate all $k$-Cliques in $G$ with $k$-delay.
The notion of ...
- 740
0
votes
0
answers
96
views
Basic Lower bound for Probabilistic Communication Complexity
I am Reading the Paper "Fourier Analysis For Probabilistic Communication Complexity" by Ran Raz, In this introduction of the paper, for deterministic protocols, if 'm' is total number of ...
4
votes
2
answers
372
views
Lower bound on the Among Us game
Among Us Problem:
There are $2n$ undercover agents in Don's lair. Fewer than $n$ of them are terrorists, and the rest are anti-terrorists. The identities are top-secret, and no external evidence can ...
- 1,463
1
vote
1
answer
279
views
On lower bound for Integer Multiplication
Is there a Matrix Multiplication style lower bound of $\Omega(n\log n)$ for Integer multiplication?
Raz showed in https://doi.org/10.1145%2F509907.509932 that mutiplying $n\times n$ matrices requires $...
- 13.8k
9
votes
1
answer
593
views
Circuits for matrix multiplication over reals can be assumed bi-linear? Looking for reference/proof
In Ran Raz's paper, top of page 3, he uses the following claim without proof or reference, saying it is well-known and easy to prove:
Let $C$ be an arithmetic circuit for multiplying two matrices over ...
- 301
5
votes
1
answer
98
views
Resources or Survey Papers on Applying Random Restrictions to Resolution Proof Lower Bound Techniques
I am currently exploring the application of the random restriction technique in proving lower bounds within the context of resolution proofs. I would like to know if there are any comprehensive ...
- 418
4
votes
0
answers
181
views
Lower bound for comparison sort without oracle
Is there a lower bound for comparison sorting where the comparison function is supplied as the encoding of a Turing machine, rather than being available as an oracle?
A bit more formally, let's say ...
5
votes
1
answer
268
views
Randomness in RAM
Is there a problem on $n$ bits that can be solved in linear time on a RAM with randomness, but we don't know how to solve in linear time without randomness?
Exclude polynomial-identity testing (see ...
- 7,861
6
votes
0
answers
207
views
Proof complexity of Sudoku
Let $P$ be a $N$x$N$ Sudoku puzzle
(assume $N=n^2$ for some $n\in \mathbb{N}$,
e.g. standard $9$x$9$ puzzle is $n=3$).
We can represent it in propositional logic as follows:
Variables
$p_{i,j,k}$: ...
- 22.2k