Nir Bitansky, Vinod Vaikuntanathan:
Indistinguishability Obfuscation from Functional Encryption
Indistinguishability Obfuscation from Functional Encryption
This paper made an important conceptual contribution by demonstrating how succinct public-key functional encryption is sufficient to construct indistinguishability obfuscation which is widely viewed as the “universal cryptographic primitive,” capable of yielding nearly any cryptographic functionality. Its techniques shaped subsequent work enabling simpler constructions and influencing a generation of follow-up research.
Mika Göös, Toniann Pitassi, Thomas Watson:
Deterministic Communication vs. Partition Number
Deterministic Communication vs. Partition Number
This paper separates the logarithm of the partition number and the deterministic communication complexity of a function, resolving a long-standing open problem and moreover, stimulating a flurry of works on lifting theorems of various kinds. Lifting, first introduced by Raz and Mckenzie, is the idea of first proving a separation in the setting of query complexity and then to “lifting” it to communication complexity.
Yin Tat Lee, Aaron Sidford, Sam Chiu-Wai Wong:
A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization
A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization
This paper showed how to solve convex programs in the cutting-plane framework, using a (near-)linear number of calls to a separation oracle while performing a (near-)cubic number of arithmetic operations. This result both improved and unified prior methods for solving this classic problem, yielding improved algorithms for submodular minimization, matroid intersection, and other combinatorial optimization problems.