5 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 ,…
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…
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{…
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…