Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Nitin Saurabh:

TR21-100 | 11th July 2021
Christian Ikenmeyer, Balagopal Komarath, Nitin Saurabh

Karchmer-Wigderson Games for Hazard-free Computation

We present a Karchmer-Wigderson game to study the complexity of hazard-free formulas. This new game is both a generalization of the monotone Karchmer-Wigderson game and an analog of the classical Boolean Karchmer-Wigderson game. Therefore, it acts as a bridge between the existing monotone and general games.

Using this game, we ... more >>>

TR20-031 | 10th March 2020
Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh

Algebraic Branching Programs, Border Complexity, and Tangent Spaces

Nisan showed in 1991 that the width of a smallest noncommutative single-(source,sink) algebraic branching program (ABP) to compute a noncommutative polynomial is given by the ranks of specific matrices. This means that the set of noncommutative polynomials with ABP width complexity at most $k$ is Zariski-closed, an important property in ... more >>>

TR18-167 | 25th September 2018
Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucky, Nitin Saurabh, Ronald de Wolf

Improved bounds on Fourier entropy and Min-entropy

Revisions: 1

Given a Boolean function $f: \{-1,1\}^n\rightarrow \{-1,1\}$, define the Fourier distribution to be the distribution on subsets of $[n]$, where each $S\subseteq [n]$ is sampled with probability $\widehat{f}(S)^2$. The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai [FK96] seeks to relate two fundamental measures associated with the Fourier distribution: does ... more >>>

TR16-038 | 15th March 2016
Meena Mahajan, Nitin Saurabh

Some Complete and Intermediate Polynomials in Algebraic Complexity Theory

Revisions: 2

We provide a list of new natural VNP-intermediate polynomial
families, based on basic (combinatorial) NP-complete problems that
are complete under \emph{parsimonious} reductions. Over finite
fields, these families are in VNP, and under the plausible
hypothesis $\text{Mod}_pP \not\subseteq P/\text{poly}$, are neither VNP-hard (even under
oracle-circuit reductions) nor in VP. Prior to ... more >>>

TR14-163 | 29th November 2014
Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh

Homomorphism polynomials complete for VP

The VP versus VNP question, introduced by Valiant, is probably the most important open question in algebraic complexity theory. Thanks to completeness results, a variant of this question, VBP versus VNP, can be succinctly restated as asking whether the permanent of a generic matrix can be written as a determinant ... more >>>

TR13-150 | 4th November 2013
Ruiwen Chen, Valentine Kabanets, Nitin Saurabh

An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas

We give a deterministic #SAT algorithm for de Morgan formulas of size up to $n^{2.63}$, which runs in time $2^{n-n^{\Omega(1)}}$. This improves upon the deterministic #SAT algorithm of \cite{CKKSZ13}, which has similar running time but works only for formulas of size less than $n^{2.5}$.

Our new algorithm is based on ... more >>>

TR13-052 | 3rd April 2013
Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, Nitin Saurabh

{Upper Bounds on Fourier Entropy

Revisions: 2

iven a function $f : \{0,1\}^n \to \reals$, its {\em Fourier Entropy} is defined to be $-\sum_S \fcsq{f}{S} \log \fcsq{f}{S}$, where $\fhat$ denotes the Fourier transform of $f$. This quantity arises in a number of applications, especially in the study of Boolean functions. An outstanding open question is a conjecture ... more >>>

ISSN 1433-8092 | Imprint