1 citations · 2 across the 13 of their papers we have counts for
11 papers · 1 filter
Binary Huffman Coding with Unequal Letter Costs Is NP-Complete
L. Sunil Chandran, Rishikesh Gajjala
Binary prefix coding assigns prefix-free binary words to symbols to minimize their frequency-weighted cost. Huffman solved the equal-letter-cost case in polynomial time in 1952 [Pr…
Asymptotically Optimal Weighted Edge Colorings via Local Bin Packing
Rishikesh Gajjala, Arindam Khan
We study weighted edge coloring, where each edge of a graph has a weight in , and colors are assigned so that the incident weight of each color at every vertex is at mos…
Geometric Graph Representations via Compact SAT Encodings
L. Sunil Chandran, Rishikesh Gajjala, Suraj Kumar Sahoo +1
We present compact SAT encodings and certifying exact solvers for boxicity and cubicity. The boxicity of a graph is the minimum dimension in which it is the intersection graph of a…
Connectivity Bounds for GHZ Graphs
L. Sunil Chandran, Rishikesh Gajjala
Greenberger-Horne-Zeilinger (GHZ) states are multipartite entangled quantum states that play a central role in quantum information theory, with applications in quantum communicatio…
Towards Learning-Guided Discovery of Extremal Geometric Constructions: A PatternBoost Study
Deepak Ajwani, Paula Carroll, Rishikesh Gajjala +5
Extremal constructions play a central role in the design and analysis of algorithms. Integrality-gap instances expose the limitations of relaxations, while hard configurations reve…
Random Garbage Creates Exponential Quantum Query Separations
Khaled Elbassioni, Rishikesh Gajjala, Saurabh Ray
We prove an exponential separation between standard (XOR) quantum queries and forward-erasing queries for a Boolean property of injective functions, answering a question of Aaronso…
Tight Approximation Thresholds for Geometric Stabbing
Khaled Elbassioni, Rishikesh Gajjala, Saurabh Ray
We study geometric covering problems: stabbing axis-parallel squares and cubes by coordinate hyperplanes, stabbing horizontal segments by horizontal and vertical lines, and transve…
Two-copy nondistillability of Werner states: sharp partial-trace inequalities and finite-copy extensions
Kishor Bharti, Rishikesh Gajjala, Tobias Haug
We solve the two-copy distillability problem for Werner states in every local dimension. Our main matrix result is a sharp, dimension-free inequality: for every rank-at-most-two op…
Counterexamples to Wegner's Conjecture for Rectangles
Deepak Ajwani, Rishikesh Gajjala, Rajiv Raman +1
Wegner conjectured in 1965 that every finite family of axis-parallel rectangles satisfies , where is the minimum num…
Counterexamples to an Extremal Conjecture for Random Cycle-Factors
Rishikesh Gajjala
Christoph, Draganić, Girão, Hurley, Michel, and Müyesser conjectured that, when , the expected number of cycles in a uniformly random cycle-factor of a directed -regula…
W-state graphs: Structure and Algorithms
Rishikesh Gajjala, Saurabh Ray, Dimitrios M. Thilikos
We study the class of edge-coloured graphs arising from the graph-theoretic representation of quantum photonic experiments that generate multipartite W-states. Abstracting away phy…