Jonathan Tidor

activity

20132026

most citedEquiangular lines with a fixed angle

65 citations · 108 across the 25 of their papers we have counts for

collaborators

27 papers

math.CO2026

The Erdős distinct distances problem in $R^{3}$

Jonathan Tidor, Hung-Hsun Hans Yu, Dmitrii Zakharov

We prove that $N$ points in $R^{3}$ determine at least $N^{2/3 - o (1)}$ distinct distances.

math.CO2026

$K_{2, t + 1}$ -free graphs with many copies of $K_{t, t}$

Cosmin Pohoata, Jonathan Tidor, Hung-Hsun Hans Yu

For every fixed integer $t \geq 3$ , we construct an $n$ -vertex $K_{2, t + 1}$ -free graph containing $Ω_{t} (n^{2})$ copies of $K_{t, t}$ . Combined with a simple counting argument, this shows…

cs.CG2026

Separators for intersection graphs of spheres

Jacob Fox, Jonathan Tidor

We prove the existence of optimal separators for intersection graphs of balls and spheres in any dimension $d$ . One of our results is that if an intersection graph of $n$ spheres i…

math.CO2024

On monochromatic solutions to linear equations over the integers

Dingding Dong, Nitya Mani, Huy Tuan Pham +1

We study the number of monochromatic solutions to linear equations in a $2$ -coloring of ${1, \dots, n}$ . We show that any nontrivial linear equation has a constant fraction of sol…

math.CO2024

More unit distances in arbitrary norms

Josef Greilhuber, Carl Schildkraut, Jonathan Tidor

For $d \geq 2$ and any norm on $R^{d}$ , we prove that there exists a set of $n$ points that spans at least $(\frac{d}{2} - o (1)) n lo g_{2} n$ unit distances under this norm for every…

math.CO2024

Multilevel polynomial partitioning and semialgebraic hypergraphs: regularity, Turán, and Zarankiewicz results

Jonathan Tidor, Hung-Hsun Hans Yu

We prove three main results about semialgebraic hypergraphs. First, we prove an optimal and oblivious regularity lemma. Fox, Pach, and Suk proved that the class of $k$ -uniform semi…

math.CO2023

Ramsey and Turán numbers of sparse hypergraphs

Jacob Fox, Maya Sankar, Michael Simkin +2

Degeneracy plays an important role in understanding Turán- and Ramsey-type properties of graphs. Unfortunately, the usual hypergraphical generalization of degeneracy fails to captu…

math.CO2023★ 1 cited

Triangle Ramsey numbers of complete graphs

Jacob Fox, Jonathan Tidor, Shengtong Zhang

A graph is $H$ -Ramsey if every two-coloring of its edges contains a monochromatic copy of $H$ . Define the $F$ -Ramsey number of $H$ , denoted by $r_{F} (H)$ , to be the minimum number of…

math.CO2023

Uniform sets with few progressions via colorings

Mingyang Deng, Jonathan Tidor, Yufei Zhao

Ruzsa asked whether there exist Fourier-uniform subsets of $Z / N Z$ with density $α$ and 4-term arithmetic progression (4-AP) density at most $α^{C}$ , for arbitrarily l…

cs.DS2022

Cubic Goldreich-Levin

Dain Kim, Anqi Li, Jonathan Tidor

In this paper, we give a cubic Goldreich-Levin algorithm which makes polynomially-many queries to a function $f : F_{p}^{n} \to C$ and produces a decomposition of…

math.CO2021

Quantitative bounds for the $U^{4}$ -inverse theorem over low characteristic finite fields

Jonathan Tidor

This paper gives the first quantitative bounds for the inverse theorem for the Gowers $U^{4}$ -norm over $F_{p}^{n}$ when $p = 2, 3$ . We build upon earlier work of Gowers and Miliće…

math.CO2021★ 3 cited

Non-classical polynomials and the inverse theorem

Aaron Berger, Ashwin Sah, Mehtaab Sawhney +1

In this note we characterize when non-classical polynomials are necessary in the inverse theorem for the Gowers $U^{k}$ -norm. We give a brief deduction of the fact that a bounded fun…

math.CO2021★ 11 cited

Popular differences for matrix patterns

Aaron Berger, Ashwin Sah, Mehtaab Sawhney +1

The following combinatorial conjecture arises naturally from recent ergodic-theoretic work of Ackelsberg, Bergelson, and Best. Let $M_{1}$ , $M_{2}$ be $k \times k$ integer matrices, $G$ …

cs.DS2020

Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost

Aaron Berger, William Kuszmaul, Adam Polak +2

We study the basic problem of assigning memoryless workers to tasks with dynamically changing demands. Given a set of $w$ workers and a multiset $T \subseteq [t]$ of $∣ T ∣ = w$ tasks,…

math.CO2020★ 2 cited

Joints of varieties

Jonathan Tidor, Hung-Hsun Hans Yu, Yufei Zhao

We generalize the Guth--Katz joints theorem from lines to varieties. A special case says that $N$ planes (2-flats) in 6 dimensions (over any field) have $O (N^{3/2})$ joints, where…

math.CO2020★ 9 cited

Spherical two-distance sets and eigenvalues of signed graphs

Zilin Jiang, Jonathan Tidor, Yuan Yao +2

We study the problem of determining the maximum size of a spherical two-distance set with two fixed angles (one acute and one obtuse) in high dimensions. Let $N_{α, β} (d)$ denote th…

math.CO2020

A counterexample to the Bollobás-Riordan conjectures on sparse graph limits

Ashwin Sah, Mehtaab Sawhney, Jonathan Tidor +1

Bollobás and Riordan, in their paper "Metrics for sparse graphs," proposed a number of provocative conjectures extending central results of quasirandom graphs and graph limits to s…

math.CO2019★ 3 cited

Induced arithmetic removal: complexity 1 patterns over finite fields

Jacob Fox, Jonathan Tidor, Yufei Zhao

We prove an arithmetic analog of the induced graph removal lemma for complexity 1 patterns over finite fields. Informally speaking, we show that given a fixed collection of $r$ -col…

math.CO2019★ 3 cited

Testing linear-invariant properties

Jonathan Tidor, Yufei Zhao

Fix a prime $p$ and a positive integer $R$ . We study the property testing of functions $F_{p}^{n} \to [R]$ . We say that a property is testable if there exists an oblivious tester…

math.CO2019★ 65 cited

Equiangular lines with a fixed angle

Zilin Jiang, Jonathan Tidor, Yuan Yao +2

Solving a longstanding problem on equiangular lines, we determine, for each given fixed angle and in all sufficiently large dimensions, the maximum number of lines pairwise separat…

cs.DS2018

Spectral methods for testing cluster structure of graphs

Sandeep Silwal, Jonathan Tidor

In the framework of graph property testing, we study the problem of determining if a graph admits a cluster structure. We say that a graph is $(k, ϕ)$ -clusterable if it can be part…

math.CO2018★ 2 cited

Hypergraph expanders of all uniformities from Cayley graphs

David Conlon, Jonathan Tidor, Yufei Zhao

Hypergraph expanders are hypergraphs with surprising, non-intuitive expansion properties. In a recent paper, the first author gave a simple construction, which can be randomized, o…

math.CO2016★ 1 cited

1-color-avoiding paths, special tournaments, and incidence geometry

Jonathan Tidor, Victor Y. Wang, Ben Yang

We discuss two approaches to a recent question of Loh: must a 3-colored transitive tournament on $N$ vertices have a 1-color-\emph{avoiding} path of vertex-length at least $N^{2/3}…

math.CO2015★ 6 cited

Dense binary $P G (t - 1, 2)$ -free matroids have critical number $t - 1$ or $t$

Jonathan Tidor

The critical threshold of a (simple binary) matroid $N$ is the infimum over all $ρ$ such that any $N$ -free matroid $M$ with $∣ M ∣ > ρ 2^{r (M)}$ has bounded critical number. In this…

The Erdős distinct distances problem in R3

K2,t+1​-free graphs with many copies of Kt,t​

Separators for intersection graphs of spheres

On monochromatic solutions to linear equations over the integers

More unit distances in arbitrary norms

Multilevel polynomial partitioning and semialgebraic hypergraphs: regularity, Turán, and Zarankiewicz results

Ramsey and Turán numbers of sparse hypergraphs

Triangle Ramsey numbers of complete graphs

Uniform sets with few progressions via colorings

Cubic Goldreich-Levin

Quantitative bounds for the U4-inverse theorem over low characteristic finite fields

Non-classical polynomials and the inverse theorem

Popular differences for matrix patterns

Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost

Joints of varieties

Spherical two-distance sets and eigenvalues of signed graphs

A counterexample to the Bollobás-Riordan conjectures on sparse graph limits

Induced arithmetic removal: complexity 1 patterns over finite fields

Testing linear-invariant properties

Equiangular lines with a fixed angle

Spectral methods for testing cluster structure of graphs

Hypergraph expanders of all uniformities from Cayley graphs

1-color-avoiding paths, special tournaments, and incidence geometry

Dense binary PG(t−1,2)-free matroids have critical number t−1 or t

The Erdős distinct distances problem in $R^{3}$

$K_{2, t + 1}$ -free graphs with many copies of $K_{t, t}$

Quantitative bounds for the $U^{4}$ -inverse theorem over low characteristic finite fields

Dense binary $P G (t - 1, 2)$ -free matroids have critical number $t - 1$ or $t$