research
∙
08/21/2023
Dimension Independent Helly Theorem for Lines and Flats
We give a generalization of dimension independent Helly Theorem of Adipr...
share
research
∙
08/21/2023
Stabbing boxes with finitely many axis-parallel lines and flats
We give necessary and sufficient condition for an infinite collection of...
research
∙
08/04/2023
Linear isomorphism testing of Boolean functions with small approximate spectral norm
Two Boolean functions f, g : F_2^n →-1, 1 are called linearly isomorphic...
research
∙
01/09/2023
Sparse Geometric Set Systems and the Beck-Fiala Conjecture
We investigate the combinatorial discrepancy of geometric set systems ha...
research
∙
12/28/2022
Heterochromatic Higher Order Transversals for Convex Sets
In this short paper, we show that if {ℱ_n}_n ∈ℕ be a collection of famil...
research
∙
07/28/2022
Colorful Helly Theorem for Piercing Boxes with Two Points
Let h(d,2) denote the smallest integer such that any finite collection o...
research
∙
07/27/2022
An optimal generalization of Alon and Füredi's covering result
Given an n-cube 𝒬^n := {0,1}^n in ℝ^n, the k-th layer 𝒬^n_k of 𝒬^n denot...
research
∙
07/25/2022
Testing of Index-Invariant Properties in the Huge Object Model
The study of distribution testing has become ubiquitous in the area of p...
research
∙
04/26/2022
Tolerant Bipartiteness Testing in Dense Graphs
Bipartite testing has been a central problem in the area of property tes...
research
∙
01/13/2022
Faster Counting and Sampling Algorithms using Colorful Decision Oracle
In this work, we consider d-Hyperedge Estimation and d-Hyperedge Sample ...
research
∙
11/19/2021
Uniform Brackets, Containers, and Combinatorial Macbeath Regions
We study the connections between three seemingly different combinatorial...
research
∙
10/19/2021
Exploring the Gap between Tolerant and Non-tolerant Distribution Testing
The framework of distribution testing is currently ubiquitous in the fie...
research
∙
10/09/2021
A Faster Algorithm for Max Cut in Dense Graphs
We design an algorithm for approximating the size of Max Cut in dense gr...
research
∙
10/08/2021
Bipartite Independent Set Oracles and Beyond: Can it Even Count Triangles in Polylogarithmic Queries?
Beame et al. [ITCS 2018] introduced and used the Bipartite Independent S...
research
∙
07/06/2021
Distance Estimation Between Unknown Matrices Using Sublinear Projections on Hamming Cube
Using geometric techniques like projection and dimensionality reduction,...
research
∙
07/17/2020
Query Complexity of Global Minimum Cut
In this work, we resolve the query complexity of global minimum cut prob...
research
∙
06/24/2020
Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond
The disjointness problem - where Alice and Bob are given two subsets of ...
research
∙
08/12/2019
Hyperedge Estimation using Polylogarithmic Subset Queries
A hypergraph H is a set system (U( H), F(H)), where U( H) denotes the s...
research
∙
06/18/2019
Inner Product Oracle can Estimate and Sample
Edge estimation problem in unweighted graphs using local and sometimes g...
research
∙
06/13/2019
Structural Parameterization for Graph Deletion Problems over Data Streams
The study of parameterized streaming complexity on graph problems was in...
research
∙
06/13/2019
Fixed-Parameter Tractability of Graph Deletion Problems over Data Streams
In this work, we initiate a systematic study of parameterized streaming ...
research
∙
08/02/2018
Triangle Estimation using Polylogarithmic Queries
Estimating the number of triangles in a graph is one of the most fundame...
research
∙
07/17/2018
Parameterized Query Complexity of Hitting Set using Stability of Sunflowers
In this paper, we study the query complexity of parameterized decision a...
research
∙
04/19/2018
Delaunay simplices in diagonally distorted lattices
Delaunay protection is a measure of how far a Delaunay triangulation is ...
research
∙
03/20/2018
Local criteria for triangulation of manifolds
We present criteria for establishing a triangulation of a manifold. Give...
research
∙
03/19/2018
On the streaming complexity of fundamental geometric problems
In this paper, we focus on lower bounds and algorithms for some basic ge...
research
∙
01/10/2018
FPT algorithms for embedding into low complexity graphic metrics
The Metric Embedding problem takes as input two metric spaces (X,D_X) an...
research
∙
08/05/2017