1 citations · 2 across the 5 of their papers we have counts for
8 papers
On Disperser/Lifting Properties of the Index and Inner-Product Functions
Paul Beame, Sajin Koroth
Query-to-communication lifting theorems, which connect the query complexity of a Boolean function to the communication complexity of an associated `lifted' function obtained by com…
Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality
Mohammad Mahdi Jahanara, Sajin Koroth, Igor Shinkar
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 theoret…
Automating Cutting Planes is NP-Hard}
Mika Göös, Sajin Koroth, Ian Mertz +1
We show that Cutting Planes (CP) proofs are hard to find: Given an unsatisfiable formula , 1) It is NP-hard to find a CP refutation of in time polynomial in the length of th…
Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates
Valentine Kabanets, Sajin Koroth, Zhenjian Lu +2
The class consists of Boolean functions computable by size- de Morgan formulas whose leaves are any Boolean functions from a class .…
Query-to-Communication Lifting Using Low-Discrepancy Gadgets
Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth +2
Lifting theorems are theorems that relate the query complexity of a function to the communication complexity of the composed function , for…
Depth Lower Bounds against Circuits with Sparse Orientation
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 is the characteristic vector of the…
A Study on Hierarchical Floorplans of Order k
Shankar Balachandran, Sajin Koroth
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 cro…
Sub-families of Baxter Permutations Based on Pattern Avoidance
Shankar Balachandran, Sajin Koroth
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…