Yuval Filmus

According to our database, Yuval Filmus authored at least 89 papers between 2010 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Limits of Preprocessing.

Yuval Filmus, Yuval Ishai, Avi Kaplan, Guy Kindler

Comput. Complex., June, 2024

Optimal Sets of Questions for Twenty Questions.

Yuval Filmus, Idan Mehalel

SIAM J. Discret. Math., March, 2024

Sparse juntas on the biased hypercube.

Irit Dinur, Yuval Filmus, Prahladh Harsha

TheoretiCS, 2024

Special Section on the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (2020).

Yuval Filmus, Elena Grigorescu, Sungjin Im, Yi Li

SIAM J. Comput., 2024

Lifting dichotomies.

Yaroslav Alekseev, Yuval Filmus, Alexander Smal

Electron. Colloquium Comput. Complex., 2024

Separating Coverage and Submodular: Maximization Subject to a Cardinality Constraint.

Yuval Filmus, Roy Schwartz, Alexander V. Smal

CoRR, 2024

Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs.

Yuval Filmus, Steve Hanneke, Idan Mehalel, Shay Moran

CoRR, 2024

Sparse Graph Counting and Kelley-Meka Bounds for Binary Systems.

Yuval Filmus, Hamed Hatami, Kaave Hosseini, Esty Kelman

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

2023

Sampling and Certifying Symmetric Functions.

Yuval Filmus, Itai Leigh, Artur Riazanov, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2023

Proving Unsatisfiability with Hitting Formulas.

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

Electron. Colloquium Comput. Complex., 2023

Generalized Polymorphisms.

Gilad Chase, Yuval Filmus

CoRR, 2023

Irreducible Subcube Partitions.

Yuval Filmus, Edward A. Hirsch, Sascha Kurz, Ferdinand Ihringer, Artur Ryazanov, Alexander V. Smal, Marc Vinyals

Electron. J. Comb., 2023

Junta Threshold for Low Degree Boolean Functions on the Slice.

Yuval Filmus

Electron. J. Comb., 2023

Bounded Simultaneous Messages.

Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, Sruthi Sekar

Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023

Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension.

Yuval Filmus, Steve Hanneke, Idan Mehalel, Shay Moran

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

Irreducible subcube partitions.

Yuval Filmus, Edward A. Hirsch, Sascha Kurz, Ferdinand Ihringer, Artur Riazanov, Alexander Smal, Marc Vinyals

CoRR, 2022

Simple Algebraic Proofs of Uniqueness for Erdős-Ko-Rado Theorems.

Yuval Filmus, Nathan Lindzey

CoRR, 2022

Approximate polymorphisms.

Gilad Chase, Yuval Filmus, Dor Minzer, Elchanan Mossel, Nitin Saurabh

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

A Resilient Distributed Boosting Algorithm.

Yuval Filmus, Idan Mehalel, Shay Moran

Proceedings of the International Conference on Machine Learning, 2022

2021

Query-to-Communication Lifting Using Low-Discrepancy Gadgets.

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

SIAM J. Comput., 2021

Tight Approximation for Unconstrained XOS Maximization.

Yuval Filmus, Yasushi Kawase, Yusuke Kobayashi, Yutaro Yamaguchi

Math. Oper. Res., 2021

Bounded Indistinguishability for Simple Sources.

Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, Akshayaram Srinivasan

Electron. Colloquium Comput. Complex., 2021

Almost linear Boolean functions on S_n are almost unions of cosets.

Yuval Filmus

CoRR, 2021

Revisiting the Complexity Analysis of Conflict-Based Search: New Computational Techniques and Improved Bounds.

Ofir Gordon, Yuval Filmus, Oren Salzman

Proceedings of the Fourteenth International Symposium on Combinatorial Search, 2021

Shrinkage Under Random Projections, and Cubic Formula Lower Bounds for AC0 (Extended Abstract).

Yuval Filmus, Or Meir, Avishay Tal

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Explicit SoS Lower Bounds from High-Dimensional Expanders.

Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

The Entropy of Lies: Playing Twenty Questions with a Liar.

Yuval Dagan, Yuval Filmus, Daniel Kane, Shay Moran

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Complexity Measures on the Symmetric Group and Beyond (Extended Abstract).

Neta Dafni, Yuval Filmus, Noam Lifshitz, Nathan Lindzey, Marc Vinyals

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

2020

Special Issue: CCC 2019: Guest Editor's Foreword.

Yuval Filmus

Theory Comput., 2020

Online submodular maximization: beating 1/2 made simple.

Niv Buchbinder, Moran Feldman, Yuval Filmus, Mohit Garg

Math. Program., 2020

Shrinkage under Random Projections, and Cubic Formula Lower Bounds for AC⁰.

Yuval Filmus, Or Meir, Avishay Tal

Electron. Colloquium Comput. Complex., 2020

MaxSAT Resolution and Subcube Sums.

Yuval Filmus, Meena Mahajan, Gaurav Sood, Marc Vinyals

Electron. Colloquium Comput. Complex., 2020

Explicit and structured sum of squares lower bounds from high dimensional expanders.

Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani

Electron. Colloquium Comput. Complex., 2020

FKN theorem for the multislice, with applications.

Yuval Filmus

Comb. Probab. Comput., 2020

Complexity Measures on the Symmetric Group and Beyond.

Neta Dafni, Yuval Filmus, Noam Lifshitz, Nathan Lindzey, Marc Vinyals

CoRR, 2020

Hypercontractivity on the symmetric group.

Yuval Filmus, Guy Kindler, Noam Lifshitz, Dor Minzer

CoRR, 2020

A Sauer-Shelah-Perles Lemma for Lattices.

Stijn Cambie, Bogdan Chornomaz, Zeev Dvir, Yuval Filmus, Shay Moran

Electron. J. Comb., 2020

AND testing and robust judgement aggregation.

Yuval Filmus, Noam Lifshitz, Dor Minzer, Elchanan Mossel

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

2019

Another look at degree lower bounds for polynomial calculus.

Yuval Filmus

Theor. Comput. Sci., 2019

Analyzing Power in Weighted Voting Games with Super-Increasing Weights.

Yuval Filmus, Joel Oren, Yair Zick, Yoram Bachrach

Theory Comput. Syst., 2019

Boolean degree 1 functions on some classical association schemes.

Yuval Filmus, Ferdinand Ihringer

J. Comb. Theory A, 2019

Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions.

Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami, David Zuckerman

Electron. Colloquium Comput. Complex., 2019

Boolean constant degree functions on the slice are juntas.

Yuval Filmus, Ferdinand Ihringer

Discret. Math., 2019

More complete intersection theorems.

Yuval Filmus

Discret. Math., 2019

Asymptotic performance of the Grimmett-McDiarmid heuristic.

Yuval Filmus

CoRR, 2019

Twenty (Short) Questions.

Yuval Dagan, Yuval Filmus, Ariel Gabizon, Shay Moran

Comb., 2019

Information Complexity of the AND Function in the Two-Party and Multi-party Settings.

Yuval Filmus, Hamed Hatami, Yaqiao Li, Suzin You

Algorithmica, 2019

Analyzing Boolean functions on the biased hypercube via higher-dimensional agreement tests: [Extended abstract].

Irit Dinur, Yuval Filmus, Prahladh Harsha

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

A Log-Sobolev Inequality for the Multislice, with Applications.

Yuval Filmus, Ryan O'Donnell, Xinyu Wu

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Query-To-Communication Lifting for BPP Using Inner Product.

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

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

Invariance Principle on the Slice.

Yuval Filmus, Guy Kindler, Elchanan Mossel, Karl Wimmer

ACM Trans. Comput. Theory, 2018

Boolean function analysis on high-dimensional expanders.

Irit Dinur, Yotam Dikstein, Yuval Filmus, Prahladh Harsha

Electron. Colloquium Comput. Complex., 2018

Boolean functions on high-dimensional expanders.

Yotam Dikstein, Irit Dinur, Yuval Filmus, Prahladh Harsha

CoRR, 2018

2017

The weighted complete intersection theorem.

Yuval Filmus

J. Comb. Theory A, 2017

Agreement tests on graphs and hypergraphs.

Irit Dinur, Yuval Filmus, Prahladh Harsha

Electron. Colloquium Comput. Complex., 2017

Low degree almost Boolean functions are sparse juntas.

Irit Dinur, Yuval Filmus, Prahladh Harsha

Electron. Colloquium Comput. Complex., 2017

Information complexity of the AND function in the two-Party, and multiparty settings.

Yuval Filmus, Hamed Hatami, Yaqiao Li, Suzin You

CoRR, 2017

Twenty (simple) questions.

Yuval Dagan, Yuval Filmus, Ariel Gabizon, Shay Moran

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

2016

Trading information complexity for error.

Yuval Dagan, Yuval Filmus, Hamed Hatami, Yaqiao Li

Electron. Colloquium Comput. Complex., 2016

Shapley Values in Weighted Voting Games with Random Weights.

Yuval Filmus, Joel Oren, Kannan Soundararajan

CoRR, 2016

An Orthogonal Basis for Functions over a Slice of the Boolean Hypercube.

Yuval Filmus

Electron. J. Comb., 2016

Friedgut-Kalai-Naor Theorem for Slices of the Boolean Cube.

Yuval Filmus

Chic. J. Theor. Comput. Sci., 2016

Semantic Versus Syntactic Cutting Planes.

Yuval Filmus, Pavel Hrubes, Massimo Lauria

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

A Characterization of Voting Power for Discrete Weight Distributions.

Yoram Bachrach, Yuval Filmus, Joel Oren, Yair Zick

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, 2016

Harmonicity and Invariance on Slices of the Boolean Cube.

Yuval Filmus, Elchanan Mossel

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

Exponential Lower Bounds for AC⁰-Frege Imply Superpolynomial Frege Lower Bounds.

Yuval Filmus, Toniann Pitassi, Rahul Santhanam

ACM Trans. Comput. Theory, 2015

Space Complexity in Polynomial Calculus.

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

SIAM J. Comput., 2015

A stability result for balanced dictatorships in S_n.

David Ellis, Yuval Filmus, Ehud Friedgut

Random Struct. Algorithms, 2015

A quasi-stability result for dictatorships in S n.

David Ellis, Yuval Filmus, Ehud Friedgut

Comb., 2015

Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method.

Andris Ambainis, Yuval Filmus, François Le Gall

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

2014

Spectral Methods in Extremal Combinatorics.

Yuval Filmus

PhD thesis, 2014

The complexity of the comparator circuit value problem.

Stephen A. Cook, Yuval Filmus, Dai Tri Man Le

ACM Trans. Comput. Theory, 2014

Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search.

Yuval Filmus, Justin Ward

SIAM J. Comput., 2014

From Small Space to Small Width in Resolution.

Yuval Filmus, Massimo Lauria, Mladen Miksa, Jakob Nordström, Marc Vinyals

Electron. Colloquium Comput. Complex., 2014

Fast Matrix Multiplication: Limitations of the Laser Method.

Andris Ambainis, Yuval Filmus, François Le Gall

Electron. Colloquium Comput. Complex., 2014

Power Distribution in Randomized Weighted Voting: the Effects of the Quota.

Joel Oren, Yuval Filmus, Yair Zick, Yoram Bachrach

CoRR, 2014

A SageTeX Hypermatrix Algebra Package.

Edinah K. Gnang, Ori Parzanchevski, Yuval Filmus

CoRR, 2014

Bounds on the sum of L1 influences.

Yuval Filmus, Hamed Hatami

CoRR, 2014

Efficient voting via the top-k elicitation scheme: a probabilistic approach.

Yuval Filmus, Joel Oren

Proceedings of the ACM Conference on Economics and Computation, 2014

2013

Inequalities on submodular functions via term rewriting.

Yuval Filmus

Inf. Process. Lett., 2013

Average Case Lower Bounds for Monotone Switching Networks.

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

Electron. Colloquium Comput. Complex., 2013

Universal codes of the natural numbers.

Yuval Filmus

Log. Methods Comput. Sci., 2013

Efficient Vote Elicitation under Candidate Uncertainty.

Joel Oren, Yuval Filmus, Craig Boutilier

Proceedings of the IJCAI 2013, 2013

Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds - (Extended Abstract).

Yuval Filmus, Massimo Lauria, Mladen Miksa, Jakob Nordström, Marc Vinyals

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

The Power of Local Search: Maximum Coverage over a Matroid.

Yuval Filmus, Justin Ward

Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

Automatic web-scale information extraction.

Philip Bohannon, Nilesh N. Dalvi, Yuval Filmus, Nori Jacoby, S. Sathiya Keerthi, Alok Kirpal

Proceedings of the ACM SIGMOD International Conference on Management of Data, 2012

A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint.

Yuval Filmus, Justin Ward

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011

Lower bounds for context-free grammars.

Yuval Filmus

Inf. Process. Lett., 2011

2010

Threshold Models for Competitive Influence in Social Networks.

Allan Borodin, Yuval Filmus, Joel Oren

Proceedings of the Internet and Network Economics - 6th International Workshop, 2010