3 papers
math.PR2025
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…
cs.CC2025
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…
cs.CC2022
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…