Submodularity Is Barely Testable

In 2010, Seshadhri and Vondrák asked: is submodularity testable? For functions $f : \{ 0, 1 \}^n \to \mathbb{R}$, they gave a tester that makes $2^{O(\sqrt{n} \log n)}$ queries. We show that every tester, even an adaptive one with two-sided error, must make $2^{Ω(\sqrt{n})}$ queries, thereby concluding: submodularity is barely testable.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-02
DOI
https://doi.org/10.48550/arxiv.2611.02374
Primary Topic
Complexity and Algorithms in Graphs
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

Submodularity Is Barely Testable

Diptaksho Palit, Yuichi Yoshida
arXiv (Cornell University)
Complexity and Algorithms in Graphs
preprint

Submodularity Is Barely Testable

Diptaksho Palit, Yuichi Yoshida
preprint en

Abstract

In 2010, Seshadhri and Vondrák asked: is submodularity testable? For functions $f : \{ 0, 1 \}^n \to \mathbb{R}$, they gave a tester that makes $2^{O(\sqrt{n} \log n)}$ queries. We show that every tester, even an adaptive one with two-sided error, must make $2^{Ω(\sqrt{n})}$ queries, thereby concluding: submodularity is barely testable.

arXiv (Cornell University)
Complexity and Algorithms in Graphs
DOIOpen Access PDFOpenAlex
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon
Submodularity Is Barely Testable — Diptaksho Palit, Yuichi Yoshida · arXiv (Cornell University) (2026) | TGRS Research Map | TGRS