4 papers
Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
Susanna F. de Rezende, David Engström, Yassine Ghannane +2
We study the average-case hardness of establishing that a graph does not have a large clique in both proof and communication complexity. We show exponential lower bounds on the len…
Partial Minimum Branching Program Size Problem is ETH-hard
Ludmila Glinskih, Artur Riazanov
We show that assuming the Exponential Time Hypothesis, the Partial Minimum Branching Program Size Problem (MBPSP*) requires superpolynomial time. This result also applies to the pa…
Sampling and Certifying Symmetric Functions
Yuval Filmus, Itai Leigh, Artur Riazanov +1
A circuit samples a distribution with an error if the statistical distance between the output of on the uniform input and …
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…