On CC^0 Lower Bounds for AND via Torus Polynomials by Jayalal Sarma @ICTStalks
On CC^0 Lower Bounds for AND via Torus Polynomials by Jayalal Sarma  @ICTStalks
Uploaded September 2026 | Updated November 2026, 2 days ago
Program: Circuits, Communication, and Proofs

ORGANIZERS: Arkadev Chattopadhyay (TIFR, Mumbai, India) and Meena Mahajan (IMSc, Chennai, India)

DATE & TIME: 10 August 2026 to 21 August 2026

VENUE: Ramanujan Lecture Hall, ICTS Bengaluru

Theoretical computer science in general, and computational complexity theory in particular, offers a new lens to look at the other natural and mathematical sciences, and is having a significant impact in those other fields. The main goal of computational complexity theory is the study of the (in)feasibility of efficient computation. Proof complexity, originating from mathematical logic, examines the strength of logical reasoning approaches rather than directly reasoning with computation. The Cook-Reckhow program aims to ultimately show that in every propositional proof system, there exist true statements that do not have short efficiently verifiable proofs; this is equivalent to separating NP from coNP, an even harder problem than the notorious P=?NP problem. The modern networked world with shared resources drives home the point that both computation and communication are equally valued resources. Complexity theorists have increasingly realized that the study of communication bottlenecks, in a simple model proposed by Yao 40 years ago, often holds the key to proving the non-existence of efficient algorithms. This happens in a remarkable variety of situations.

The strands of circuit complexity, query/communication complexity, and proof complexity have a lot to offer each other in terms of tools, techniques, and questions. In the last decade, the interplay between these strands has really flourished – communication complexity theoretic techniques have been heavily used in propositional proof complexity; lower bounds on the sizes of proofs, via communication complexity arguments, have implied lower bounds on size of monotone circuits; lifting theorems have allowed non-trivial transfer of lower bounds across models, etc.

In this 2-week program, the first week will be in the form of a boot camp, with a series of lectures on each of the three strands mentioned above. The second week will feature research talks, giving participants exposure to current developments in the areas.

CONTACT US: ccproofs@icts.res.in
PROGRAM LINK: icts.res.in/program/ccp
On CC^0 Lower Bounds for AND via Torus Polynomials by Jayalal SarmaAn introduction to the Macroscopic Fluctuation Theory for Diffusive Systems by Bernard DerridaOptimal Transport, Wasserstein Gradient Flows, and the JKO Sc.. (Lecture 3)  by Filippo SantambrogioConjugacy Between Bosonic and Classical Ornstein–Uhlenbeck Semigroups by Alberto De SoleGeneralized Symmetries on the Lattice: A Tensor Network Point of View by Frank VerstraeteHypertoric geometry of Coulomb branches (Lecture 1) by Lorenzo FoscoloHypertoric Geometry of Coulomb Branches (Lecture 4) by Lorenzo FoscoloExact Fluctuation Theory for Product-Kernel Aggregation, Instantons, Non-Convex Large.. by R. RajeshA Gentle Introduction to Large Deviations(Lecture 5)  by Parthanil RoyTurbulence Theory by Ozgur GurcanTranslation and Industrial Ecosystem by Suchismita Sanyal, Mallikarjun KarraThermal Boundary Conditions in Fractional Superdiffusion of Energy by Tomasz Komorowski
International Centre for Theoretical Sciences |

On CC^0 Lower Bounds for AND via Torus Polynomials by Jayalal Sarma

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER