Hamed Hatami

SIGACT News, March, 2024

Typical structure of hereditary properties of binary matroids.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2024

Structure in Communication Complexity and Constant-Cost Complexity Classes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2024

A Lower Bound on the Trace Norm of Boolean Matrices and its Applications.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2024

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

[BibT_eX]

[DOI]

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

Communication Complexity and Discrepancy of Halfplanes.

[BibT_eX]

[DOI]

Proceedings of the 40th International Symposium on Computational Geometry, 2024

2023

Refuting approaches to the log-rank conjecture for XOR functions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

Communication complexity of half-plane membership.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

A tight lower bound on non-adaptive group testing estimation.

[BibT_eX]

[DOI]

Tsun-Ming Cheung

Anthony Ostuni

CoRR, 2023

A Borsuk-Ulam Lower Bound for Sign-Rank and Its Applications.

[BibT_eX]

[DOI]

Xiang Meng

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Online Learning and Disambiguations of Partial Concept Classes.

[BibT_eX]

[DOI]

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022

On public-coin zero-error randomized communication complexity.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2022

Lower Bound Methods for Sign-rank and their Limitations.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

A Borsuk-Ulam lower bound for sign-rank and its application.

[BibT_eX]

[DOI]

Xiang Meng

Electron. Colloquium Comput. Complex., 2022

Boolean functions with small approximate spectral norm.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Separation of the factorization norm and randomized communication complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

A counter-example to the probabilistic universal graph conjecture via randomized communication complexity.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2022

On depth-3 circuits and covering number: an explicit counter-example.

[BibT_eX]

[DOI]

Ndiamé Ndiaye

CoRR, 2022

The Implicit Graph Conjecture is False.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Dimension-free Bounds and Structural Results in Communication Complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Approximation Algorithms for Hitting Subgraphs.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 32nd International Workshop, 2021

2020

Lower bounds for graph bootstrap percolation via properties of polynomials.

[BibT_eX]

[DOI]

Yingjie Qian

J. Comb. Theory A, 2020

2019

Higher-order Fourier Analysis and Applications.

[BibT_eX]

[DOI]

Found. Trends Theor. Comput. Sci., 2019

Sign rank vs Discrepancy.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

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

[BibT_eX]

[DOI]

Algorithmica, 2019

2018

Structure of Protocols for XOR Functions.

[BibT_eX]

[DOI]

SIAM J. Comput., 2018

Graph properties, graph limits, and entropy.

[BibT_eX]

[DOI]

Svante Janson

Balázs Szegedy

J. Graph Theory, 2018

2017

The Unbounded-Error Communication Complexity of symmetric XOR functions.

[BibT_eX]

[DOI]

Yingjie Qian

CoRR, 2017

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

[BibT_eX]

[DOI]

CoRR, 2017

2016

A characterization of functions with vanishing averages over products of disjoint sets.

[BibT_eX]

[DOI]

Yaqiao Li

Eur. J. Comb., 2016

Trading information complexity for error.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

On the Additive Bases Problem in Finite Fields.

[BibT_eX]

[DOI]

Victoria de Quehen

Electron. J. Comb., 2016

2014

Correlation Testing for Affine Invariant Properties on 픽pn in the High Error Regime.

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

The inducibility of blow-up graphs.

[BibT_eX]

[DOI]

James Hirst

Serguei Norine

J. Comb. Theory B, 2014

General systems of linear forms: equidistribution and true complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Bounds on the sum of L1 influences.

[BibT_eX]

[DOI]

Yuval Filmus

CoRR, 2014

Limits of Boolean Functions on 𝔽pn.

[BibT_eX]

[DOI]

James Hirst

Electron. J. Comb., 2014

2013

On the number of pentagons in triangle-free graphs.

[BibT_eX]

[DOI]

Alexander A. Razborov

J. Comb. Theory A, 2013

Estimating the distance from testable affine-invariant properties.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

The Entropy of Random-Free Graphons and Properties.

[BibT_eX]

[DOI]

Serguei Norine

Comb. Probab. Comput., 2013

2012

The scaling window for a random graph with a given degree sequence.

[BibT_eX]

[DOI]

Michael Molloy

Random Struct. Algorithms, 2012

Every locally characterized affine-invariant property is testable.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Non-Three-Colourable Common Graphs Exist.

[BibT_eX]

[DOI]

Alexander A. Razborov

Comb. Probab. Comput., 2012

Spectral Norm of Symmetric Functions.

[BibT_eX]

[DOI]

Anil Ada

Omar Fawzi

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

Correlation testing for affine invariant properties on Fpn in the high error regime.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Correlation Testing for Affine Invariant Properties on $\mathbb{F}_p^n$ in the High Error Regime

[BibT_eX]

[DOI]

CoRR, 2011

2010

On Generalizations of Gowers Norms.

[BibT_eX]

[DOI]

PhD thesis, 2010

Higher-order Fourier analysis of Fpn and the complexity of systems of linear forms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

2009

The Fractional Chromatic Number of Graphs of Maximum Degree at Most Three.

[BibT_eX]

[DOI]

Xuding Zhu

SIAM J. Discret. Math., 2009

Decision Trees and Influences of Variables Over Product Probability Spaces.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2009

2008

Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to l1 Embeddability of Negative Type Metrics.

[BibT_eX]

[DOI]

Avner Magen

Evangelos Markakis

SIAM J. Discret. Math., 2008

Sharp thresholds for constraint satisfaction problems and homomorphisms.

[BibT_eX]

[DOI]

Michael Molloy

Random Struct. Algorithms, 2008

Fourier analysis and large independent sets in powers of complete graphs.

[BibT_eX]

[DOI]

Mahya Ghandehari

J. Comb. Theory B, 2008

Approximation and inapproximability results for maximum clique of disc graphs in high dimensions.

[BibT_eX]

[DOI]

Peyman Afshani

Inf. Process. Lett., 2008

2007

Perfect Dominating Sets in the Cartesian Products of Prime Cycles.

[BibT_eX]

[DOI]

Electron. J. Comb., 2007

Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to l1 Embeddability of Negative Type Metrics.

[BibT_eX]

[DOI]

Avner Magen

Evangelos Markakis

Proceedings of the Approximation, 2007

2005

Circular chromatic index of graphs of maximum degree 3.

[BibT_eX]

[DOI]

J. Graph Theory, 2005

Delta+300 is a bound on the adjacent vertex distinguishing edge chromatic number.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2005

Random cubic graphs are not homomorphic to the cycle of size 7.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2005

On the size of the minimum critical set of a Latin square.

[BibT_eX]

[DOI]

Mahya Ghandehari

Ebadollah S. Mahmoodian

Discret. Math., 2005

On the computational complexity of defining sets.

[BibT_eX]

[DOI]

Hossein Maserrat

Discret. Appl. Math., 2005

2004

On the complexity of the circular chromatic number.

[BibT_eX]

[DOI]

Ruzbeh Tusserkani

J. Graph Theory, 2004

On the spectrum of the forced matching number of graphs.

[BibT_eX]

[DOI]

Peyman Afshani