3 papers
cs.CC2026
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…
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…