# Questions tagged [lower-bounds]

The tag has no usage guidance.

254 questions
Filter by
Sorted by
Tagged with
29 views

### How far can we push "counting argument" for proving lower bounds of time complexity?

It's obvious that we cannot find min (or max) in an array of length n in strictly less than n "steps". It's also well-...
4 views

### Deterministic online caching algorithm competitive ratio lower bound proof

I don't understand the adversary based proof in CLRS for proving lower bound of Ω (k) on competitive ratio of any deterministic online caching algorithm given that ...
101 views

### Conditional lower bounds on the running time of the single source shortest path problem

Just out of curiosity, I was wondering whether there is a conditional lower-bound on the running time of an algorithm for the Single Source Shortest Path Problem (on directed or undirected graphs). I ...
1 vote
28 views

### Minimum number of vertices in a tree with pathwidth $h$?

Let $\mathcal{T}_h$ be the set of trees with pathwidth $h$. What is the minimum,$|V(T)|$ over all $T \in \mathcal{T}_h$. I'm guessing this is a fairly easy question. We know that a complete binary ...
77 views

### Lower Bound on Parity of Boolean Functions

Let's say we have boolean functions $f_1, \cdots, f_n$, each of which operates on pairwise disjoint variables (i.e. the variables for each function are unique to that function). Then, how can we show ...
19 views

### Analysis of Simon's Algorithm: Probability Expression for Matching Queries

The Simon's problem is that, given a function $f:\{0,1\}^n\to\{0,1\}^n$ such that, for all $x,y\{0,1\}^n$ t satisfies $$f(x)=f(y)\text{ iff }x=y\oplus s$$ where $s\in \{0,1\}^n$, and the Simon's ...
133 views

### Resolution exponential lower bound... alternative proofs?

I am reading the Resolution proof system exponential lower bound via Haken's bottleneck method for the Pigeonhole Principle as presented in Arora and Barak's Computational Complexity: A Modern ...
1 vote