6 papers
Spectral Shadows: When Communication Complexity Meets Linear Invariance Testing
Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal +2
In this short note, we initiate the study of the Linear Isomorphism Testing Problem in the setting of communication complexity, a natural linear algebraic generalization of the cla…
No Infinite -Theorem for Piercing Compact Convex Sets with Lines in
Sutanoya Chakraborty, Arijit Ghosh
An infinite -theorem, or an -theorem, involving two families and of sets, states that if in every infinite subset of ,…
Testing Isomorphism of Boolean Functions over Finite Abelian Groups
Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal +2
Let and be Boolean functions over a finite Abelian group , where is fully known, and we have {\em query access} to , that is, given any $x \in \mathcal{…
A Hanani-Tutte Theorem for Cycles
Sutanoya Chakraborty, Arijit Ghosh
Given a drawing of a graph , we define the crossing number between any two cycles and in to be the number of crossings that involve at least one edge fro…
A geometric proof of the infinite -theorem for hyperplane piercing
Sutanoya Chakraborty, Arijit Ghosh, Soumi Nandi
We provide a geometric proof of the -theorem for piercing compact connected sets by hyperplanes. Our argument uses only elementary properties of convex sets and…
Finite k-Transversals of Infinite Families of Fat Convex Sets
Sutanoya Chakraborty, Arijit Ghosh, Soumi Nandi
We prove an infinite -theorem for piercing fat compact convex sets in $\RR^d$ with -flats. Additionally, we develop a new framework through which infinite -theorem…