2 citations · 3 across the 3 of their papers we have counts for
4 papers
Michael Rabin's fingerprints across the theory of computation
Avi Wigderson
Michael O. Rabin was a major founder and leader of theoretical computer science. He died on April 14, 2026, at the age of 94. This paper aims to survey the wide scope and lasting i…
The communication complexity of distributed estimation
Parikshit Gopalan, Raghu Meka, Prasad Raghavendra +2
We study an extension of the standard two-party communication model in which Alice and Bob hold probability distributions and over domains and , respectively. Their…
Complexity of Robust Orbit Problems for Torus Actions and the abc-conjecture
Peter Bürgisser, Mahmut Levent Doğan, Visu Makam +2
When a group acts on a set, it naturally partitions it into orbits, giving rise to orbit problems. These are natural algorithmic problems, as symmetries are central in numerous que…
Constant-Depth Arithmetic Circuits for Linear Algebra Problems
Robert Andrews, Avi Wigderson
We design polynomial size, constant depth (namely, ) arithmetic formulae for the greatest common divisor (GCD) of two polynomials, as well as the related problems of…