Can the $n$-party broadcast channel, where any symbol sent by one party is received by all, be made resilient to noise with low overhead? Namely, is it possible to construct interactive error-correcting codes that convert any protocol designed for the noiseless broadcast channel into one that works over the noisy ... more >>>

In the standard model of computing multi-output functions in logspace ($\text{FL}$), we are given a read-only tape holding $x$ and a logarithmic length worktape, and must print $f(x)$ to a dedicated write-only tape. However, there has been extensive work (both in theory and in practice) on in-place algorithms for ... more >>>

Certification for Quantified Boolean Formulas (QBF) and Dependency Quantified Boolean Formulas is an ongoing challenge (DQBF). Recent proof complexity work has shown that the majority of QBF and DQBF techniques can be p-simulated by using the independent extension rule. In propositional logic, extension rules are supported by proof checkers using ... more >>>