Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Siddhartha Jain:

TR24-017 | 23rd January 2024
Siddhartha Jain, Jiawei Li, Robert Robere, Zhiyang Xun

On Pigeonhole Principles and Ramsey in TFNP

The generalized pigeonhole principle says that if tN + 1 pigeons are put into N holes then there must be a hole containing at least t + 1 pigeons. Let t-PPP denote the class of all total NP-search problems reducible to finding such a t-collision of pigeons. We introduce a ... more >>>

TR23-154 | 12th October 2023
Vishnu Iyer, Siddhartha Jain, Matt Kovacs-Deak, Vinayak Kumar, Luke Schaeffer, Daochen Wang, Michael Whitmeyer

On the Rational Degree of Boolean Functions and Applications

We study a natural complexity measure of Boolean functions known as the (exact) rational degree. For total functions $f$, it is conjectured that $\mathrm{rdeg}(f)$ is polynomially related to $\mathrm{deg}(f)$, where $\mathrm{deg}(f)$ is the Fourier degree. Towards this conjecture, we show that symmetric functions have rational degree at least $\mathrm{deg}(f)/2$ and ... more >>>

TR22-096 | 8th July 2022
Mika Göös, Siddhartha Jain

Communication Complexity of Collision

The Collision problem is to decide whether a given list of numbers $(x_1,\ldots,x_n)\in[n]^n$ is $1$-to-$1$ or $2$-to-$1$ when promised one of them is the case. We show an $n^{\Omega(1)}$ randomised communication lower bound for the natural two-party version of Collision where Alice holds the first half of the bits of ... more >>>

TR22-058 | 26th April 2022
Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao

Separations in Proof Complexity and TFNP

Revisions: 1

It is well-known that Resolution proofs can be efficiently simulated by Sherali-Adams (SA) proofs. We show, however, that any such simulation needs to exploit huge coefficients: Resolution cannot be efficiently simulated by SA when the coefficients are written in unary. We also show that Reversible Resolution (a variant of MaxSAT ... more >>>

TR22-018 | 15th February 2022
Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao

Further Collapses in TFNP

We show $\text{EOPL}=\text{PLS}\cap\text{PPAD}$. Here the class $\text{EOPL}$ consists of all total search problems that reduce to the End-of-Potential-Line problem, which was introduced in the works by Hubacek and Yogev (SICOMP 2020) and Fearnley et al. (JCSS 2020). In particular, our result yields a new simpler proof of the breakthrough collapse ... more >>>

TR21-016 | 16th February 2021
Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari

Unambiguous DNFs from Hex

Revisions: 1

We exhibit an unambiguous $k$-DNF formula that requires CNF width $\tilde{\Omega}(k^{1.5})$. Our construction is inspired by the board game Hex and it is vastly simpler than previous ones, which achieved at best an exponent of $1.22$. Our result is known to imply several other improved separations in query and communication ... more >>>

ISSN 1433-8092 | Imprint