1 citations · 1 across the 5 of their papers we have counts for
6 papers
Third and Fourth Moment Phenomena for Monochromatic Edges and Applications to Graph-Based Two-Sample Tests
Siva Athreya, Bhaswar B. Bhattacharya, Yogesh Dahiya +4
Given a graph sequence , denote by the number of monochromatic edges when the vertices of are independently colored red or blue with probabili…
Quantum-Classical Equivalence for AND-Functions
Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay +2
A major open problem in quantum communication complexity is whether quantum protocols can be exponentially more efficient than classical protocols for computing total Boolean funct…
Self-Reinforced Preferential Attachment
Yogesh Dahiya, Frank den Hollander
We consider a preferential attachment random graph with self-reinforcement. Each time a new vertex comes in, it attaches itself to an old vertex with a probability that is proporti…
Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis
Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett
A seminal result of Nisan and Szegedy (STOC, 1992) shows that for any total Boolean function, the degree of the real polynomial that computes the function, and the minimal degree o…
Urns with Multiple Drawings and Graph-Based Interaction
Yogesh Dahiya, Neeraja Sahasrabudhe
Consider a finite undirected graph and place an urn with balls of two colours at each vertex. At every discrete time step, for each urn, a fixed number of balls are drawn from that…
On (Simple) Decision Tree Rank
Yogesh Dahiya, Meena Mahajan
In the decision tree computation model for Boolean functions, the depth corresponds to query complexity, and size corresponds to storage space. The depth measure is the most well-s…