All reports by Author Sajin Koroth:

__
TR19-103
| 7th August 2019
__

Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi#### Query-to-Communication Lifting Using Low-Discrepancy Gadgets

__
TR16-076
| 27th April 2016
__

Krishnamoorthy Dinesh, Sajin Koroth, Jayalal Sarma#### Characterization and Lower Bounds for Branching Program Size using Projective Dimension

Revisions: 2

__
TR14-072
| 29th April 2014
__

Sajin Koroth, Jayalal Sarma#### Depth Lower Bounds against Circuits with Sparse Orientation

Revisions: 1

Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi

Lifting theorems are theorems that relate the query complexity of a function $f:\left\{ 0,1 \right\}^n\to \left\{ 0,1 \right\}$ to the communication complexity of the composed function $f\circ g^n$, for some “gadget” $g:\left\{ 0,1 \right\}^b\times \left\{ 0,1 \right\}^b\to \left\{ 0,1 \right\}$. Such theorems allow transferring lower bounds from query complexity to ... more >>>

Krishnamoorthy Dinesh, Sajin Koroth, Jayalal Sarma

We study projective dimension, a graph parameter (denoted by $pd(G)$ for a graph $G$), introduced by (Pudlak, Rodl 1992), who showed that proving lower bounds for $pd(G_f)$ for bipartite graphs $G_f$ associated with a Boolean function $f$ imply size lower bounds for branching programs computing $f$. Despite several attempts (Pudlak, ... more >>>

Sajin Koroth, Jayalal Sarma

We study depth lower bounds against non-monotone circuits, parametrized by a new measure of non-monotonicity: the orientation of a function $f$ is the characteristic vector of the minimum sized set of negated variables needed in any DeMorgan circuit computing $f$. We prove trade-off results between the depth and the weight/structure ... more >>>