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…
Proving Unsatisfiability with Hitting Formulas
Yuval Filmus, Edward A. Hirsch, Artur Riazanov +2
Hitting formulas have been studied in many different contexts at least since [Iwama,89]. A hitting formula is a set of Boolean clauses such that any two of them cannot be simultane…
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…
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…