178 citations
- California Institute of TechnologyUS4 papers
- Fermi National Accelerator LaboratoryUS4 papers
- University of MichiganUS4 papers
- Astrobiology CenterJP3 papers
- Astronomy and SpaceAU3 papers
- Center for Astrophysics Harvard & SmithsonianUS3 papers
- Institute for Fundamental Physics of the UniverseIT3 papers
- Institute of AstronomyRU3 papers
- Kavli Institute for Particle Astrophysics and CosmologyUS3 papers
- Netherlands Institute for Radio AstronomyNL3 papers
- Space Telescope Science InstituteUS3 papers
- Technion – Israel Institute of TechnologyIL3 papers
6 papers · 1 filter
Homomorphism Tensors and Linear Equations
Martin Grohe, Gaurav Rattan, Tim Seppelt
Lovász (1967) showed that two graphs and are isomorphic if and only if they are homomorphism indistinguishable over the class of all graphs, i.e. for every graph , the n…
Sharp density bounds on the finite field Kakeya problem
Boris Bukh, Ting-Wei Chao
A Kakeya set in is a set containing a line in every direction. We show that every Kakeya set in has density at least , matching the con…
Boolean functions on which are nearly linear
Yuval Filmus
We show that if is -close to linear in and then is -close to a union of "mostly disjoint" cosets, and moreover…
Cycle type of random permutations: A toolkit
Kevin Ford
We prove a number of results, new and old, about the cycle type of a random permutation on S_n. Underlying our analysis is the idea that the number of cycles of size k is roughly P…
Sorting probability for large Young diagrams
Swee Hong Chan, Igor Pak, Greta Panova
For a finite poset , let denote the set of linear extensions of . The sorting probability is defined as \[δ(P) \, := \, \min_{x,y\in X} \, \b…
The analytic rank of tensors and its applications
Shachar Lovett
The analytic rank of a tensor, first defined by Gowers and Wolf in the context of higher-order Fourier analysis, is defined to be the logarithm of the bias of the tensor. We prove…