The Range Avoidance ($\text{Avoid}$) problem $\mathcal{C}$-$\text{Avoid}[n,m(n)]$ asks that, given a circuit in a class $\mathcal{C}$ with input length $n$ and output length $m(n)>n$, find a string not in the range of the circuit. This problem has been a central piece in several recent frameworks of proving circuit lower bounds and ... more >>>

Matching is a central problem in theoretical computer science, with a large body of work spanning the last five decades. However, understanding matching in the time-space bounded setting remains a longstanding open question, even in the presence of additional resources such as randomness or non-determinism.

In this work we study ... more >>>

Let $G$ be a finite abelian group and $A$ be a subset of $G \times G$ which is corner--free, meaning that there are no $x, y \in G$ and $d \in G \setminus \{0\}$ such that $(x, y)$, $(x+d, y)$, $(x, y+d) \in A$. We prove that
$|A| \le |G|^2 ... more >>>