Showing cs.CCShow all
3 papers · 1 filter
cs.CC2026
No Constant-Cost Protocol for Point--Line Incidence
Mika Göös, Nathaniel Harms, Florian K. Richter +1
Alice and Bob are given -bit integer pairs and , respectively, and they must decide if . We prove that the randomised communication complexity of this Poi…
cs.CC2024
Separations in Proof Complexity and TFNP
Mika Göös, Alexandros Hollender, Siddhartha Jain +4
It is well-known that Resolution proofs can be efficiently simulated by Sherali-Adams (SA) proofs. We show, however, that any such simulation needs to exploit huge coefficients: Re…
cs.CC2024
Top-Down Lower Bounds for Depth-Four Circuits
Mika Göös, Artur Riazanov, Anastasia Sofronova +1
We present a top-down lower-bound method for depth- boolean circuits. In particular, we give a new proof of the well-known result that the parity function requires depth- cir…