Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Pritish Kamath:

TR17-175 | 13th November 2017
Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov

Monotone Circuit Lower Bounds from Resolution

For any unsatisfiable CNF formula $F$ that is hard to refute in the Resolution proof system, we show that a gadget-composed version of $F$ is hard to refute in any proof system whose lines are computed by efficient communication protocols---or, equivalently, that a monotone function associated with $F$ has large ... more >>>

TR17-125 | 7th August 2017
Badih Ghazi, Pritish Kamath, Prasad Raghavendra

Dimension Reduction for Polynomials over Gaussian Space and Applications

In this work we introduce a new technique for reducing the dimension of the ambient space of low-degree polynomials in the Gaussian space while preserving their relative correlation structure. As applications, we address the following problems:

(I) Computability of the Approximately Optimal Noise Stable function over Gaussian space:

The goal ... more >>>

TR17-024 | 16th February 2017
Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson

Query-to-Communication Lifting for P^NP

We prove that the $\text{P}^{\small\text{NP}}$-type query complexity (alternatively, decision list width) of any boolean function $f$ is quadratically related to the $\text{P}^{\small\text{NP}}$-type communication complexity of a lifted version of $f$. As an application, we show that a certain "product" lower bound method of Impagliazzo and Williams (CCC 2010) fails to ... more >>>

TR16-194 | 4th December 2016
Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald Rivest, Madhu Sudan

The Optimality of Correlated Sampling

In the "correlated sampling" problem, two players, say Alice and Bob, are given two distributions, say $P$ and $Q$ respectively, over the same universe and access to shared randomness. The two players are required to output two elements, without any interaction, sampled according to their respective distributions, while trying to ... more >>>

TR16-104 | 14th July 2016
Badih Ghazi, Pritish Kamath, Madhu Sudan

Decidability of Non-Interactive Simulation of Joint Distributions

We present decidability results for a sub-class of "non-interactive" simulation problems, a well-studied class of problems in information theory. A non-interactive simulation problem is specified by two distributions $P(x,y)$ and $Q(u,v)$: The goal is to determine if two players, Alice and Bob, that observe sequences $X^n$ and $Y^n$ respectively where ... more >>>

TR15-087 | 30th May 2015
Badih Ghazi, Pritish Kamath, Madhu Sudan

Communication Complexity of Permutation-Invariant Functions

Motivated by the quest for a broader understanding of communication complexity of simple functions, we introduce the class of ''permutation-invariant'' functions. A partial function $f:\{0,1\}^n \times \{0,1\}^n\to \{0,1,?\}$ is permutation-invariant if for every bijection $\pi:\{1,\ldots,n\} \to \{1,\ldots,n\}$ and every $\mathbf{x}, \mathbf{y} \in \{0,1\}^n$, it is the case that $f(\mathbf{x}, \mathbf{y}) ... more >>>

TR13-026 | 11th February 2013
Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

Arithmetic circuits: A chasm at depth three

Revisions: 1

We show that, over $\mathbb{C}$, if an $n$-variate polynomial of degree $d = n^{O(1)}$ is computable by an arithmetic circuit of size $s$ (respectively by an algebraic branching program of size $s$) then it can also be computed by a depth three circuit (i.e. a $\Sigma \Pi \Sigma$-circuit) of size ... more >>>

TR12-098 | 3rd August 2012
Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

An exponential lower bound for homogeneous depth four arithmetic circuits with bounded bottom fanin

Revisions: 3

Agrawal and Vinay (FOCS 2008) have recently shown that an exponential lower bound for depth four homogeneous circuits with bottom layer of $\times$ gates having sublinear fanin translates to an exponential lower bound for a general arithmetic circuit computing the permanent. Motivated by this, we examine the complexity of computing ... more >>>

ISSN 1433-8092 | Imprint