Source author record

Sajin Koroth

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity Discrete Mathematics math.CO

Catalog footprint

Research overview

7works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates

The class $FORMULA[s] \circ \mathcal{G}$ consists of Boolean functions computable by size- $s$ de Morgan formulas whose leaves are any Boolean functions from a class $\mathcal{G}$ . We give lower bounds and (SAT, Learning, and PRG) algorithms for $FORMULA[n^{1.99}]\circ \mathcal{G}$ , for classes $\mathcal{G}$ of functions with low communication complexity. Let $R^{(k)}(\mathcal{G})$ be the maximum $k$ -party NOF randomized communication complexity of $\mathcal{G}$ . We show: (1) The Generalized Inner Product function $GIP^k_n$ cannot be computed in $FORMULA[s]\circ \mathcal{G}$ on more than $1/2+\varepsilon$ fraction of inputs for $s = o \! \left ( \frac{n^2}{ \left(k \cdot 4^k \cdot {R}^{(k)}(\mathcal{G}) \cdot \log (n/\varepsilon) \cdot \log(1/\varepsilon) \right)^{2}} \right).$ As a corollary, we get an average-case lower bound for $GIP^k_n$ against $FORMULA[n^{1.99}]\circ PTF^{k-1}$ . (2) There is a PRG of seed length $n/2 + O\left(\sqrt{s} \cdot R^{(2)}(\mathcal{G}) \cdot\log(s/\varepsilon) \cdot \log (1/\varepsilon) \right)$ that $\varepsilon$ -fools $FORMULA[s] \circ \mathcal{G}$ . For $FORMULA[s] \circ LTF$ , we get the better seed length $O\left(n^{1/2}\cdot s^{1/4}\cdot \log(n)\cdot \log(n/\varepsilon)\right)$ . This gives the first non-trivial PRG (with seed length $o(n)$ ) for intersections of $n$ half-spaces in the regime where $\varepsilon \leq 1/n$ . (3) There is a randomized $2^{n-t}$ -time $\#$ SAT algorithm for $FORMULA[s] \circ \mathcal{G}$ , where $t=Ω\left(\frac{n}{\sqrt{s}\cdot\log^2(s)\cdot R^{(2)}(\mathcal{G})}\right)^{1/2}.$ In particular, this implies a nontrivial #SAT algorithm for $FORMULA[n^{1.99}]\circ LTF$ . (4) The Minimum Circuit Size Problem is not in $FORMULA[n^{1.99}]\circ XOR$ . On the algorithmic side, we show that $FORMULA[n^{1.99}] \circ XOR$ can be PAC-learned in time $2^{O(n/\log n)}$ .

preprint2020arXiv

Automating Cutting Planes is NP-Hard}

We show that Cutting Planes (CP) proofs are hard to find: Given an unsatisfiable formula $F$ , 1) It is NP-hard to find a CP refutation of $F$ in time polynomial in the length of the shortest such refutation; and 2)unless Gap-Hitting-Set admits a nontrivial algorithm, one cannot find a tree-like CP refutation of $F$ in time polynomial in the length of the shortest such refutation. The first result extends the recent breakthrough of Atserias and Müller (FOCS 2019) that established an analogous result for Resolution. Our proofs rely on two new lifting theorems: (1) Dag-like lifting for gadgets with many output bits. (2) Tree-like lifting that simulates an $r$ -round protocol with gadgets of query complexity $O(\log r)$ independent of input length.

preprint2020arXiv

Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality

Non-signaling strategies are a generalization of quantum strategies that have been studied in physics over the past three decades. Recently, they have found applications in theoretical computer science, including to proving inapproximability results for linear programming and to constructing protocols for delegating computation. A central tool for these applications is probabilistically checkable proof (PCPs) systems that are sound against non-signaling strategies. In this paper we show, assuming a certain geometrical hypothesis about noise robustness of non-signaling proofs (or, equivalently, about robustness to noise of solutions to the Sherali-Adams linear program), that a slight variant of the parallel repetition of the exponential-length constant-query PCP construction due to Arora et al. (JACM 1998) is sound against non-signaling strategies with constant locality. Our proof relies on the analysis of the linearity test and agreement test (also known as the direct product test) in the non-signaling setting.

preprint2017arXiv

Characterization and Lower Bounds for Branching Program Size using Projective Dimension

We study projective dimension, a graph parameter (denoted by pd $(G)$ for a graph $G$ ), introduced by (Pudlák, Rödl 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 (Pudlák, Rödl 1992 ; Babai, Rónyai, Ganapathy 2000), proving super-linear lower bounds for projective dimension of explicit families of graphs has remained elusive. We show that there exist a Boolean function $f$ (on $n$ bits) for which the gap between the projective dimension and size of the optimal branching program computing $f$ (denoted by bpsize $(f)$ ), is $2^{Ω(n)}$ . Motivated by the argument in (Pudlák, Rödl 1992), we define two variants of projective dimension - projective dimension with intersection dimension 1 (denoted by upd $(G)$ ) and bitwise decomposable projective dimension (denoted by bitpdim $(G)$ ). As our main result, we show that there is an explicit family of graphs on $N = 2^n$ vertices such that the projective dimension is $O(\sqrt{n})$ , the projective dimension with intersection dimension $1$ is $Ω(n)$ and the bitwise decomposable projective dimension is $Ω(\frac{n^{1.5}}{\log n})$ . We also show that there exist a Boolean function $f$ (on $n$ bits) for which the gap between upd $(G_f)$ and bpsize $(f)$ is $2^{Ω(n)}$ . In contrast, we also show that the bitwise decomposable projective dimension characterizes size of the branching program up to a polynomial factor. That is, there exists a constant $c>0$ and for any function $f$ , $\textrm{bitpdim}(G_f)/6 \le \textrm{bpsize}(f) \le (\textrm{bitpdim}(G_f))^c$ . We also study two other variants of projective dimension and show that they are exactly equal to well-studied graph parameters - bipartite clique cover number and bipartite partition number respectively.

preprint2016arXiv

Sub-families of Baxter Permutations Based on Pattern Avoidance

Baxter permutations are a class of permutations which are in bijection with a class of floorplans that arise in chip design called mosaic floorplans. We study a subclass of mosaic floorplans called $HFO_k$ defined from mosaic floorplans by placing certain geometric restrictions. This naturally leads to studying a subclass of Baxter permutations. This subclass of Baxter permutations are characterized by pattern avoidance. We establish a bijection, between the subclass of floorplans we study and a subclass of Baxter permutations, based on the analogy between decomposition of a floorplan into smaller blocks and block decomposition of permutations. Apart from the characterization, we also answer combinatorial questions on these classes. We give an algebraic generating function (but without a closed form solution) for the number of permutations, an exponential lower bound on growth rate, and a linear time algorithm for deciding membership in each subclass. Based on the recurrence relation describing the class, we also give a polynomial time algorithm for enumeration. We finally prove that Baxter permutations are closed under inverse based on an argument inspired from the geometry of the corresponding mosaic floorplans. This proof also establishes that the subclass of Baxter permutations we study are also closed under inverse. Characterizing permutations instead of the corresponding floorplans can be helpful in reasoning about the solution space and in designing efficient algorithms for floorplanning.

preprint2015arXiv

Depth Lower Bounds against Circuits with Sparse Orientation

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 of the orientation vectors in any circuit $C$ computing the Clique function on an $n$ vertex graph. We prove that if $C$ is of depth $d$ and each gate computes a Boolean function with orientation of weight at most $w$ (in terms of the inputs to $C$ ), then $d \times w$ must be $Ω(n)$ . In particular, if the weights are $o(\frac{n}{\log^k n})$ , then $C$ must be of depth $ω(\log^k n)$ . We prove a barrier for our general technique. However, using specific properties of the Clique function and the Karchmer-Wigderson framework (Karchmer and Wigderson, 1988), we go beyond the limitations and obtain lower bounds when the weight restrictions are less stringent. We then study the depth lower bounds when the structure of the orientation vector is restricted. Asymptotic improvements to our results (in the restricted setting), separates NP from NC. As our main tool, we generalize Karchmer-Wigderson gamefor monotone functions to work for non-monotone circuits parametrized by the weight/structure of the orientation. We also prove structural results about orientation and prove connections between number of negations and weight of orientations required to compute a function.

preprint2011arXiv

A Study on Hierarchical Floorplans of Order k

A floorplan is a rectangular dissection which describes the relative placement of electronic modules on the chip. It is called a mosaic floorplan if there are no empty rooms or cross junctions in the rectangular dissection. We study a subclass of mosaic floorplans called hierarchical floorplans of order $k$ (abbreviated HFO- ${k}$ ). A floorplan is HFO- $k$ if it can be obtained by starting with a single rectangle and recursively embedding mosaic floorplans of at most $k$ rooms inside the rooms of intermediate floorplans. When $k=2$ this is exactly the class of slicing floorplans as the only distinct floorplans with two rooms are a room with a vertical slice and a room with a horizontal slice respectdeively. And embedding such a room is equivalent to slicing the parent room vertically/horizontally. In this paper we characterize permutations corresponding to the Abe-labeling of HFO- $k$ floorplans and also give an algorithm for identification of such permutations in linear time for any particular $k$ . We give a recurrence relation for exact number of HFO-5 floorplans with $n$ rooms which can be easily extended to any $k$ also. Based on this recurrence we provide a polynomial time algorithm to generate the number of HFO- $k$ floorplans with $n$ rooms. Considering its application in VLSI design we also give moves on HFO- $k$ family of permutations for combinatorial optimization using simulated annealing etc. We also explore some interesting properties of Baxter permutations which have a bijective correspondence with mosaic floorplans.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Sajin Koroth

Research overview

Is this your work?

7 publications

Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates

Automating Cutting Planes is NP-Hard}

Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality

Characterization and Lower Bounds for Branching Program Size using Projective Dimension

Sub-families of Baxter Permutations Based on Pattern Avoidance

Depth Lower Bounds against Circuits with Sparse Orientation

A Study on Hierarchical Floorplans of Order k

See the researcher in context

Building this map preview