All reports by Author Ian Mertz:

__
TR22-026
| 17th February 2022
__

James Cook, Ian Mertz#### Trading Time and Space in Catalytic Branching Programs

__
TR21-054
| 14th April 2021
__

James Cook, Ian Mertz#### Encodings and the Tree Evaluation Problem

__
TR20-111
| 24th July 2020
__

Ian Mertz, Toniann Pitassi#### Lifting: As Easy As 1,2,3

Revisions: 1

__
TR20-056
| 17th April 2020
__

James Cook, Ian Mertz#### Catalytic Approaches to the Tree Evaluation Problem

__
TR20-049
| 17th April 2020
__

Mika Göös, Sajin Koroth, Ian Mertz, Toniann Pitassi#### Automating Cutting Planes is NP-Hard

James Cook, Ian Mertz

An $m$-catalytic branching program (Girard, Koucky, McKenzie 2015) is a set of $m$ distinct branching programs for $f$ which are permitted to share internal (i.e. non-source non-sink) nodes. While originally introduced as a non-uniform analogue to catalytic space, this also gives a natural notion of amortized non-uniform space complexity for ... more >>>

James Cook, Ian Mertz

We show that the Tree Evaluation Problem with alphabet size $k$ and height $h$ can be solved by branching programs of size $k^{O(h/\log h)} + 2^{O(h)}$. This answers a longstanding challenge of Cook et al. (2009) and gives the first general upper bound since the problem's inception.

more >>>Ian Mertz, Toniann Pitassi

Query-to-communication lifting theorems translate lower bounds on query complexity to lower bounds for the corresponding communication model. In this paper, we give a simplified proof of deterministic lifting (in both the tree-like and dag-like settings). Whereas previous proofs used sophisticated Fourier analytic techniques, our proof uses elementary counting together with ... more >>>

James Cook, Ian Mertz

The study of branching programs for the Tree Evaluation Problem, introduced by S. Cook et al. (TOCT 2012), remains one of the most promising approaches to separating L from P. Given a label in $[k]$ at each leaf of a complete binary tree and an explicit function in $[k]^2 \to ... more >>>

Mika Göös, Sajin Koroth, Ian Mertz, Toniann Pitassi

We show that Cutting Planes (CP) proofs are hard to find: Given an unsatisfiable formula $F$,

(1) it is NP-hard to find a CP refutation of $F$ in time polynomial in the length of the shortest such refutation; and

(2) unless Gap-Hitting-Set admits a nontrivial algorithm, one cannot find a ... more >>>