Mathematics and computation. A theory revolutionizing technology and science

DOI10.1515/9780691192543MaRDI QIDQ4554784zbMATH OpenOpenAlexFDO

Authors A. Wigderson

Publication date 9 November 2018

Full work available at URL https://doi.org/10.1515/9780691192543

zbMATH Keywords

arithmetic complexitycommunication complexitycomplexity classescomplexity theorycomputational complexitycomputational learning theorycryptographydistributed computingNP-completenessonline algorithmsP vs NP problempolynomial hierarchyproof complexityproof systemspseudo-randomnessquantum computingrandomnesstheory of computation

Mathematics Subject Classification ID

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) General topics in the theory of computing (68Q01) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 2133317
• Computational Complexity
• scientific article; zbMATH DE number 610968
• Computational Complexity
• Randomness -- a computational complexity perspective

Cited in

(33)

• Symmetry in Fourier analysis: Heisenberg group to Stein-Weiss integrals
• Mixing time of fractional random walk on finite fields
• Unlabeled sample compression schemes and corner peelings for ample and maximum classes
• Graph theory -- a survey on the occasion of the Abel Prize for László Lovász
• Bounds on Kronecker coefficients via contingency tables
• Moment subset sums over finite fields
• Sex: the power of randomization
• Inevitable randomness in discrete mathematics
• scientific article; zbMATH DE number 2133317 (Why is no real title available?)
• Bilevel optimization, deep learning and fractional Laplacian regularization with applications in tomography
• Unlabeled sample compression schemes and corner peelings for ample and maximum classes
• Multi-experiment parameter identifiability of ODEs and model theory
• The argument against quantum computers
• The complexity theory companion
• Interactions of computational complexity theory and mathematics
• Computability and complexity. Foundations and tools for pursuing scientific applications
• Many bounded versions of undecidable problems are \textsf{NP}-hard
• Computational complexity of counting coincidences
• Equality cases of the Alexandrov-Fenchel inequality are not in the polynomial hierarchy
• Diagonalization Games
• On the codimension of permanental varieties
• On the physical basis for the incomparability of NP and BQP
• Polynomial time classical versus quantum algorithms for representation theoretic multiplicities
• Positivity of Schubert coefficients
• Spectral Pseudorandomness and the Road to Improved Clique Number Bounds for Paley Graphs
• Almost-Ramanujan expanders from arbitrary expanders via operator amplification
• Ranks of tensors: geometry and applications
• Stability analysis of spectral technique for three-connected fractional stochastic integro-delay differential systems
• Pseudo-random number generation with -encoders
• Encounters in symbolic computation: ideas for the ages
• Is the space complexity of planted clique recovery the same as that of detection?
• Border apolarity and varieties of sums of powers
• The millennium problem about computational intractability

This page was built for publication: Mathematics and computation. A theory revolutionizing technology and science

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4554784)