Improved Lower Bounds for Testing Triangle-freeness in Boolean Functions via Fast Matrix Multiplication

DOI10.4230/LIPIcs.APPROX-RANDOM.2014.669zbMath1359.68101arXiv1308.1643OpenAlexW2964073278MaRDI QIDQ2969654

Hu Fu, Robert D. Kleinberg

Publication date: 22 March 2017

Full work available at URL: https://arxiv.org/abs/1308.1643

zbMATH Keywords

property testingfast matrix multiplicationlinear invarianceuniquely solvable puzzles

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Combinatorics in computer science (68R05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (06E30)

Related Items (8)

Removal lemmas and approximate homomorphisms ⋮ Universal points in the asymptotic spectrum of tensors ⋮ A tight bound for Green's arithmetic triangle removal lemma in vector spaces ⋮ Sunflowers and testing triangle-freeness of functions ⋮ Asymptotic tensor rank of graph tensors: beyond matrix multiplication ⋮ On arithmetic progressions in symmetric sets in finite field model ⋮ The asymptotic induced matching number of hypergraphs: balanced binary strings ⋮ Lower bounds for testing triangle-freeness in Boolean functions

This page was built for publication: Improved Lower Bounds for Testing Triangle-freeness in Boolean Functions via Fast Matrix Multiplication