Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > 2019:
All reports in year 2019:
TR19-008 | 20th January 2019
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 >>> TR19-007 | 17th January 2019 Arkadev Chattopadhyay, Meena Mahajan, Nikhil Mande, Nitin Saurabh #### Lower Bounds for Linear Decision Lists 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 >>> TR19-006 | 17th January 2019 Anna Gal, Ridwan Syed #### Upper Bounds on Communication in terms of Approximate Rank 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 >>> TR19-005 | 16th January 2019 Omar Alrabiah, Venkatesan Guruswami #### An Exponential Lower Bound on the Sub-Packetization of MSR Codes 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 >>> TR19-004 | 11th January 2019 Amey Bhangale, Subhash Khot #### UG-hardness to NP-hardness by Losing Half 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 >>> TR19-003 | 2nd January 2019 Alexander A. Sherstov, Pei Wu #### Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0 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 >>> TR19-002 | 31st December 2018 Alexander Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir Podolskii #### Complexity of Linear Operators 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 >>>

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

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 >>>

ISSN 1433-8092 | Imprint