6 papers
Cores Characterize the One-Pass Streaming Complexity of CSPs
Joshua Brakensiek, Aaron Putterman, Amatya Sharma +1
We study the one-pass streaming complexity of CSPs over a fixed finite relation under three natural objectives: , deciding whether all constraints can be satis…
Non-Redundancy of Low-Arity Symmetric Boolean CSPs
Amatya Sharma, Santhoshini Velusamy
Non-redundancy, introduced by Bessiere, Carbonnel, and Katsirelos (AAAI 2020), is a structural parameter for Constraint Satisfaction Problems () that governs kerneli…
Characterizing Streaming Decidability of CSPs via Non-Redundancy
Amatya Sharma, Santhoshini Velusamy
We study the single-pass streaming complexity of deciding satisfiability of Constraint Satisfaction Problems (CSPs). A CSP is specified by a constraint language , that is, a fin…
Tight Approximation Algorithms for Two Dimensional Guillotine Strip Packing
Arindam Khan, Aditya Lonkar, Arnab Maiti +2
In the Strip Packing problem (SP), we are given a vertical half-strip and a set of axis-aligned rectangles of width at most . The goal is to find a n…
On Guillotine Separable Packings for the Two-dimensional Geometric Knapsack Problem
Arindam Khan, Arnab Maiti, Amatya Sharma +1
In two-dimensional geometric knapsack problem, we are given a set of n axis-aligned rectangular items and an axis-aligned square-shaped knapsack. Each item has integral width, inte…
On Parameterized Complexity of Liquid Democracy
Palash Dey, Arnab Maiti, Amatya Sharma
In liquid democracy, each voter either votes herself or delegates her vote to some other voter. This gives rise to what is called a delegation graph. To decide the voters who event…