# Questions tagged [lower-bounds]

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

230 questions
Filter by
Sorted by
Tagged with
76 views

### Time-space trade-offs and towards a quadratic lower bound for $3SAT$ with $m=O(n)$ clauses?

We have quadratic $TISP$ lower bound for $SAT$. What are the known barriers preventing from getting a true quadratic circuit lower bound for $SAT$? We know from sparsification lemma that $3SAT$ ...
32 views

### Lowerbound to sample complexity or run-time of doing sparse-coding

I noticed this interesting analogous discussion that happened here, Lower bound proof for compressive sensing (Gel'fand widths)? What is the closest analogue know for such a result for sparse-...
170 views

314 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 ...
2k views

### Fourier coefficients Boolean Functions described by Bounded Depth Circuits with AND OR and XOR gates

Let $f$ be a Boolean function and let's think about f as a function from $\{-1,1\}^n$ to $\{ -1,1 \}$. In this language the Fourier expansion of f is simply the expansion of f in terms of square free ...
43 views

105 views

### Petri net termination

Termination is the following problem. Input: a Petri Net with initial marking Output: "yes" iff there exists an infinite firing sequence. The naive algorithm in the case of bounded nets for example ...
1k views

184 views

### Is $NEXP^{NP}$ known to not be contained in $NP/poly$?

To the best of my knowledge, it is known that $NEXP^{NP} \nsubseteq P/poly$, but it's still not known if $NEXP \nsubseteq P/poly$. For more info, see "Superpolynomial circuits, almost sparse oracles ...
762 views

### Succinct data structures survey?

Fischer's paper this month reminded me how little I know about the art of succinct data structures, and algorithms to use them. For those that don't know about succinct data structures: Given a ...
189 views

161 views

### Circuit's with gate computing only “simple” functions

I was curious if something like that is known or was studied. Let's call a function simple if it is computable by $AC_0$ circuit of depth $\leq d$ and size $\leq n^k$ for fixed $k,d$. Now let's ...