Pith. sign in

REVIEW 1 cited by

On generalized corners and matrix multiplication

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2309.03878 v1 pith:6ELMXBK7 submitted 2023-09-07 math.CO cs.DMcs.DS

classification math.COcs.DMcs.DS
keywords omegavarepsilondeltaboundboundscksu05cornersknown
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

Suppose that $S \subseteq [n]^2$ contains no three points of the form $(x,y), (x,y+\delta), (x+\delta,y')$, where $\delta \neq 0$. How big can $S$ be? Trivially, $n \le |S| \le n^2$. Slight improvements on these bounds are obtained from Shkredov's upper bound for the corners problem [Shk06], which shows that $|S| \le O(n^2/(\log \log n)^c)$ for some small $c > 0$, and a construction due to Petrov [Pet23], which shows that $|S| \ge \Omega(n \log n/\sqrt{\log \log n})$. Could it be that for all $\varepsilon > 0$, $|S| \le O(n^{1+\varepsilon})$? We show that if so, this would rule out obtaining $\omega = 2$ using a large family of abelian groups in the group-theoretic framework of Cohn, Kleinberg, Szegedy and Umans [CU03,CKSU05] (which is known to capture the best bounds on $\omega$ to date), for which no barriers are currently known. Furthermore, an upper bound of $O(n^{4/3 - \varepsilon})$ for any fixed $\varepsilon > 0$ would rule out a conjectured approach to obtain $\omega = 2$ of [CKSU05]. Along the way, we encounter several problems that have much stronger constraints and that would already have these implications.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability

    cs.CL 2026-08 reject novelty 7.0 of 10

    The paper introduces TCS-Bench, a 300-task proof-generation benchmark from top TCS papers, and reports frontier LLM accuracies from 30% to 68% using an automated verifier.

Pith tools