Next

__
TR24-126
| 17th June 2024
__

Takashi Ishizuka#### On the Complexity of Some Restricted Variants of Quotient Pigeon and a Weaker Variant of König

__
TR24-125
| 19th July 2024
__

Pavel Hrubes, Pushkar Joglekar#### On read-$k$ projections of the determinant

__
TR24-124
| 26th July 2024
__

Oded Goldreich#### Solving Tree Evaluation in $o(\log n \cdot \log\log n)$ space

Next

Takashi Ishizuka

One of the most famous TFNP subclasses is PPP, which is the set of all search problems whose totality is guaranteed by the pigeonhole principle. The author's recent preprint [ECCC TR24-002 2024] has introduced a TFNP problem related to the pigeonhole principle over a quotient set, called Quotient Pigeon, and ... more >>>

Pavel Hrubes, Pushkar Joglekar

We consider read-$k$ determinantal representations of polynomials and prove some non-expressibility results. A square matrix $M$ whose entries are variables or field elements will be called \emph{read-$k$}, if every variable occurs at most $k$ times in $M$. It will be called a \emph{determinantal representation} of a polynomial $f$ if $f=\det(M)$. ... more >>>

Oded Goldreich

The input to the Tree Evaluation problem is a binary tree of height $h$ in which each internal vertex is associated with a function mapping pairs of $\ell$-bit strings to $\ell$-bit strings,and each leaf is assigned an $\ell$-bit string.

The desired output is the value of the root, where ...
more >>>

Next