All reports by Author Yuval Filmus:

__
TR23-071
| 8th May 2023
__

Yuval Filmus, Itai Leigh, Artur Riazanov, Dmitry Sokolov#### Sampling and Certifying Symmetric Functions

__
TR23-016
| 22nd February 2023
__

Yuval Filmus, Edward Hirsch, Artur Riazanov, Alexander Smal, Marc Vinyals#### Proving Unsatisfiability with Hitting Formulas

__
TR20-136
| 11th September 2020
__

Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani#### Explicit and structured sum of squares lower bounds from high dimensional expanders

__
TR20-082
| 23rd May 2020
__

Yuval Filmus, Meena Mahajan, Gaurav Sood, Marc Vinyals#### MaxSAT Resolution and Subcube Sums

Revisions: 2

__
TR19-103
| 7th August 2019
__

Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi#### Query-to-Communication Lifting Using Low-Discrepancy Gadgets

Revisions: 2

__
TR18-075
| 23rd April 2018
__

Yotam Dikstein, Irit Dinur, Yuval Filmus, Prahladh Harsha#### Boolean function analysis on high-dimensional expanders

Revisions: 4

__
TR17-181
| 26th November 2017
__

Irit Dinur, Yuval Filmus, Prahladh Harsha#### Agreement tests on graphs and hypergraphs

Revisions: 1

__
TR17-180
| 26th November 2017
__

Irit Dinur, Yuval Filmus, Prahladh Harsha#### Low degree almost Boolean functions are sparse juntas

Revisions: 3

__
TR16-190
| 21st November 2016
__

Yuval Dagan, Yuval Filmus, Hamed Hatami, Yaqiao Li#### Trading information complexity for error

__
TR14-154
| 20th November 2014
__

Andris Ambainis, Yuval Filmus, Francois Le Gall#### Fast Matrix Multiplication: Limitations of the Laser Method

__
TR14-081
| 13th June 2014
__

Yuval Filmus, Massimo Lauria, Mladen Mikša, Jakob Nordström, Marc Vinyals#### From Small Space to Small Width in Resolution

__
TR13-054
| 4th April 2013
__

Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook#### Average Case Lower Bounds for Monotone Switching Networks

Revisions: 1

__
TR12-132
| 21st October 2012
__

Yuval Filmus, Massimo Lauria, Jakob Nordström, Noga Ron-Zewi, Neil Thapen#### Space Complexity in Polynomial Calculus

Yuval Filmus, Itai Leigh, Artur Riazanov, Dmitry Sokolov

A circuit $\mathcal{C}$ samples a distribution $\mathbf{X}$ with an error $\epsilon$ if the statistical distance between the output of $\mathcal{C}$ on the uniform input and $\mathbf{X}$ is $\epsilon$. We study the hardness of sampling a uniform distribution over the set of $n$-bit strings of Hamming weight $k$ denoted by $\mathbf{U}^n_k$ ... more >>>

Yuval Filmus, Edward Hirsch, Artur Riazanov, Alexander Smal, Marc Vinyals

Hitting formulas have been studied in many different contexts at least since [Iwama 1989]. A hitting formula is a set of Boolean clauses such that any two of the clauses cannot be simultaneously falsified. [Peitl and Szeider 2022] conjectured that the family of unsatisfiable hitting formulas should contain the hardest ... more >>>

Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani

We construct an explicit family of 3XOR instances which is hard for Omega(sqrt(log n)) levels of the Sum-of-Squares hierarchy. In contrast to earlier constructions, which involve a random component, our systems can be constructed explicitly in deterministic polynomial time.

Our construction is based on the high-dimensional expanders devised by Lubotzky, ...
more >>>

Yuval Filmus, Meena Mahajan, Gaurav Sood, Marc Vinyals

We study the MaxRes rule in the context of certifying unsatisfiability. We show that it can be exponentially more powerful than tree-like resolution, and when augmented with weakening (the system MaxResW), p-simulates tree-like resolution. In devising a lower bound technique specific to MaxRes (and not merely inheriting lower bounds from ... more >>>

Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi

Lifting theorems are theorems that relate the query complexity of a function $f:\left\{ 0,1 \right\}^n\to \left\{ 0,1 \right\}$ to the communication complexity of the composed function $f\circ g^n$, for some “gadget” $g:\left\{ 0,1 \right\}^b\times \left\{ 0,1 \right\}^b\to \left\{ 0,1 \right\}$. Such theorems allow transferring lower bounds from query complexity to ... more >>>

Yotam Dikstein, Irit Dinur, Yuval Filmus, Prahladh Harsha

We initiate the study of Boolean function analysis on high-dimensional expanders. We describe an analog of the Fourier expansion and of the Fourier levels on simplicial complexes, and generalize the FKN theorem to high-dimensional expanders.

Our results demonstrate that a high-dimensional expanding complex X can sometimes serve as a sparse ... more >>>

Irit Dinur, Yuval Filmus, Prahladh Harsha

Agreement tests are a generalization of low degree tests that capture a local-to-global phenomenon, which forms the combinatorial backbone of most PCP constructions. In an agreement test, a function is given by an ensemble of local restrictions. The agreement test checks that the restrictions agree when they overlap, and the ... more >>>

Irit Dinur, Yuval Filmus, Prahladh Harsha

Nisan and Szegedy showed that low degree Boolean functions are juntas. Kindler and Safra showed that low degree functions which are *almost* Boolean are close to juntas. Their result holds with respect to $\mu_p$ for every *constant* $p$. When $p$ is allowed to be very small, new phenomena emerge. ... more >>>

Yuval Dagan, Yuval Filmus, Hamed Hatami, Yaqiao Li

We consider the standard two-party communication model. The central problem studied in this article is how much one can save in information complexity by allowing an error of $\epsilon$.

For arbitrary functions, we obtain lower bounds and upper bounds indicating a gain that is of order $\Omega(h(\epsilon))$ and $O(h(\sqrt{\epsilon}))$. ...
more >>>

Andris Ambainis, Yuval Filmus, Francois Le Gall

Until a few years ago, the fastest known matrix multiplication algorithm, due to Coppersmith and Winograd (1990), ran in time $O(n^{2.3755})$. Recently, a surge of activity by Stothers, Vassilevska-Williams, and Le Gall has led to an improved algorithm running in time $O(n^{2.3729})$. These algorithms are obtained by analyzing higher ... more >>>

Yuval Filmus, Massimo Lauria, Mladen Mikša, Jakob Nordström, Marc Vinyals

In 2003, Atserias and Dalmau resolved a major open question about the resolution proof system by establishing that the space complexity of CNF formulas is always an upper bound on the width needed to refute them. Their proof is beautiful but somewhat mysterious in that it relies heavily on tools ... more >>>

Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook

An approximate computation of a Boolean function by a circuit or switching network is a computation which computes the function correctly on the majority of the inputs (rather than on all inputs). Besides being interesting in their own right, lower bounds for approximate computation have proved useful in many subareas ... more >>>

Yuval Filmus, Massimo Lauria, Jakob Nordström, Noga Ron-Zewi, Neil Thapen

During the last decade, an active line of research in proof complexity has been to study space complexity and time-space trade-offs for proofs. Besides being a natural complexity measure of intrinsic interest, space is also an important issue in SAT solving, and so research has mostly focused on weak systems ... more >>>