6 citations · 24 across the 35 of their papers we have counts for
15 papers · 1 filter
An FKN Theorem for the Binary Grassmann Scheme
Yuval Filmus, Anqi Li, Dor Minzer
A classical theorem due to Friedgut, Kalai and Naor asserts that if a function close to a degree function, then either or is close to ei…
Catalytic Computing and Register Programs Beyond Log-Depth
Yaroslav Alekseev, Yuval Filmus, Ian Mertz +2
In a seminal work, Buhrman et al. (STOC 2014) defined the class of problems solvable in space with an additional catalytic tape of size , which is a tape whose…
Bounded Simultaneous Messages
Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus +3
We consider the following question of bounded simultaneous messages (BSM) protocols: Can computationally unbounded Alice and Bob evaluate a function of their inputs by sen…
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 …
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…
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for
Yuval Filmus, Or Meir, Avishay Tal
Håstad showed that any De Morgan formula (composed of AND, OR and NOT gates) shrinks by a factor of under a random restriction…