All reports in year 2019:

__
TR19-008
| 20th January 2019
__

Ashish Dwivedi, Rajat Mittal, Nitin Saxena#### Efficiently factoring polynomials modulo $p^4$

__
TR19-007
| 17th January 2019
__

Arkadev Chattopadhyay, Meena Mahajan, Nikhil Mande, Nitin Saurabh#### Lower Bounds for Linear Decision Lists

__
TR19-006
| 17th January 2019
__

Anna Gal, Ridwan Syed#### Upper Bounds on Communication in terms of Approximate Rank

__
TR19-005
| 16th January 2019
__

Omar Alrabiah, Venkatesan Guruswami#### An Exponential Lower Bound on the Sub-Packetization of MSR Codes

__
TR19-004
| 11th January 2019
__

Amey Bhangale, Subhash Khot#### UG-hardness to NP-hardness by Losing Half

__
TR19-003
| 2nd January 2019
__

Alexander A. Sherstov, Pei Wu#### Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0

__
TR19-002
| 31st December 2018
__

Alexander Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir Podolskii#### Complexity of Linear Operators

__
TR19-001
| 5th January 2019
__

Dmitry Itsykson, Alexander Knop, Andrei Romashchenko, Dmitry Sokolov#### On OBDD-based algorithms and proof systems that dynamically change order of variables

Ashish Dwivedi, Rajat Mittal, Nitin Saxena

Polynomial factoring has famous practical algorithms over fields-- finite, rational \& $p$-adic. However, modulo prime powers it gets hard as there is non-unique factorization and a combinatorial blowup ensues. For example, $x^2+p \bmod p^2$ is irreducible, but $x^2+px \bmod p^2$ has exponentially many factors! We present the first randomized poly($\deg ... more >>>

Arkadev Chattopadhyay, Meena Mahajan, Nikhil Mande, Nitin Saurabh

We demonstrate a lower bound technique for linear decision lists, which are decision lists where the queries are arbitrary linear threshold functions.

We use this technique to prove an explicit lower bound by showing that any linear decision list computing the function $MAJ \circ XOR$ requires size $2^{0.18 n}$. This ...
more >>>

Anna Gal, Ridwan Syed

We show that any Boolean function with approximate rank $r$ can be computed by bounded error quantum protocols without prior entanglement of complexity $O( \sqrt{r} \log r)$. In addition, we show that any Boolean function with approximate rank $r$ and discrepancy $\delta$ can be computed by deterministic protocols of complexity ... more >>>

Omar Alrabiah, Venkatesan Guruswami

An $(n,k,\ell)$-vector MDS code is a $\mathbb{F}$-linear subspace of $(\mathbb{F}^\ell)^n$ (for some field $\mathbb{F}$) of dimension $k\ell$, such that any $k$ (vector) symbols of the codeword suffice to determine the remaining $r=n-k$ (vector) symbols. The length $\ell$ of each codeword symbol is called the sub-packetization of the code. Such a ... more >>>

Amey Bhangale, Subhash Khot

The $2$-to-$2$ Games Theorem of [KMS-1, DKKMS-1, DKKMS-2, KMS-2] implies that it is NP-hard to distinguish between Unique Games instances with assignment satisfying at least $(\frac{1}{2}-\varepsilon)$ fraction of the constraints $vs.$ no assignment satisfying more than $\varepsilon$ fraction of the constraints, for every constant $\varepsilon>0$. We show that the reduction ... more >>>

Alexander A. Sherstov, Pei Wu

The threshold degree of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is the minimum degree of a real polynomial $p$ that represents $f$ in sign: $\mathrm{sgn}\; p(x)=(-1)^{f(x)}.$ A related notion is sign-rank, defined for a Boolean matrix $F=[F_{ij}]$ as the minimum rank of a real matrix $M$ with $\mathrm{sgn}\; M_{ij}=(-1)^{F_{ij}}$. Determining the maximum ... more >>>

Alexander Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir Podolskii

Let $A \in \{0,1\}^{n \times n}$ be a matrix with $z$ zeroes and $u$ ones and $x$ be an $n$-dimensional vector of formal variables over a semigroup $(S, \circ)$. How many semigroup operations are required to compute the linear operator $Ax$?

As we observe in this paper, this problem contains ... more >>>

Dmitry Itsykson, Alexander Knop, Andrei Romashchenko, Dmitry Sokolov

In 2004 Atserias, Kolaitis and Vardi proposed OBDD-based propositional proof systems that prove unsatisfiability of a CNF formula by deduction of identically false OBDD from OBDDs representing clauses of the initial formula. All OBDDs in such proofs have the same order of variables. We initiate the study of OBDD based ... more >>>