Random low-degree polynomials are hard to approximate
type: Item
instance of: scholarly article
title: Random low-degree polynomials are hard to approximate
zbMATH Open document ID: 1280.68090
author: Ido Ben-Eliezer
author: Rani Hod
author: Shachar Lovett
published in: Computational Complexity
publication date: 2012-06-26T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q87
Mathematics Subject Classification ID: 94B05
Mathematics Subject Classification ID: 94B65
zbMATH DE Number: 6050362
zbMATH Keywords: random polynomials
zbMATH Keywords: Reed-Muller codes
MaRDI profile type: Publication
full work available at URL: s00037-011-0020-6
OpenAlex ID: W2032742263
cites work: On the density of sets of vectors
cites work: Small Sample Spaces Cannot Fool Low Degree Polynomials
cites work: Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
cites work: Affine dispersers from subspace polynomials
cites work: Q4342497
cites work: On the trace of finite sets
cites work: Q3549710
cites work: A new proof of Szemerédi's theorem
cites work: Q4255576
cites work: On the weight structure of Reed-Muller codes
cites work: On the weight enumeration of weights less than 2.5d of Reed—Muller codes
cites work: Weight Distribution and List-Decoding Size of Reed–Muller Codes
cites work: Set Systems with Restricted Cross-Intersections and the Minimum Rank ofInclusion Matrices
cites work: Q4146667
cites work: Hardness vs randomness
cites work: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
DOI: 10.1007/S00037-011-0020-6
description: scientific article; zbMATH DE number 6050362