research
∙
08/22/2023
Tight Lower Bound on Equivalence Testing in Conditional Sampling Model
We study the equivalence testing problem where the goal is to determine ...
share
research
∙
07/08/2023
On the Composition of Randomized Query Complexity and Approximate Degree
For any Boolean functions f and g, the question whether R(f∘ g) = Θ̃(R(f...
research
∙
06/17/2023
Approximate Model Counting: Is SAT Oracle More Powerful than NP Oracle?
Given a Boolean formula ϕ over n variables, the problem of model countin...
research
∙
06/05/2023
On simple expectations and observations of intelligent agents: A complexity study
Public observation logic (POL) reasons about agent expectations and agen...
research
∙
01/24/2023
Distinct Elements in Streams: An Algorithm for the (Text) Book
Given a data stream 𝒟 = ⟨ a_1, a_2, …, a_m ⟩ of m elements where each a_...
research
∙
11/07/2022
Certificate games
We introduce and study Certificate Game complexity, a measure of complex...
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/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
∙
05/02/2022
On verifying expectations and observations of intelligent agents
Public observation logic (POL) is a variant of dynamic epistemic logic t...
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
∙
03/23/2021
Separations between Combinatorial Measures for Transitive Functions
The role of symmetry in Boolean functions f:{0,1}^n →{0,1} has been exte...
research
∙
12/09/2020
Symmetry and Quantum Query-to-Communication Simulation
Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean fun...
research
∙
12/03/2020
Tight Chang's-lemma-type bounds for Boolean functions
Chang's lemma (Duke Mathematical Journal, 2002) is a classical result wi...
research
∙
10/24/2020
On Testing of Samplers
Given a set of items ℱ and a weight function 𝚠𝚝: ℱ↦ (0,1), the problem o...
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
∙
09/23/2019
Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead
Buhrman, Cleve and Wigderson (STOC'98) observed that for every Boolean f...
research
∙
03/27/2019
Fourier Entropy-Influence Conjecture for Random Linear Threshold Functions
The Fourier-Entropy Influence (FEI) Conjecture states that for any Boole...
research
∙
09/30/2018
Two new results about quantum exact learning
We present two new results about exact learning by quantum computers. Fi...
research
∙
09/26/2018
Improved bounds on Fourier entropy and Min-entropy
Given a Boolean function f:{-1,1}^n→{-1,1}, the Fourier distribution ass...
research
∙
09/24/2018
The Balanced Connected Subgraph Problem
The problem of computing induced subgraphs that satisfy some specified r...
research
∙
05/23/2018