5 citations · 5 across the 5 of their papers we have counts for
6 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…
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…
Irreducible subcube partitions
Yuval Filmus, Edward Hirsch, Sascha Kurz +4
A \emph{subcube partition} is a partition of the Boolean cube into subcubes. A subcube partition is irreducible if the only sub-partitions whose union is a subcube are…