Non-commutative arithmetic circuits with division

DOI10.1145/2554797.2554805MaRDI QIDQ2988867zbMATH OpenOpenAlexFDO

Authors A. Wigderson, Pavel Hrubeš

Publication date 19 May 2017

Published in Proceedings of the 5th conference on Innovations in theoretical computer science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2554797.2554805

zbMATH Keywords

arithmetic circuit complexityfree skew fieldnon-commutative rational function

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Symbolic computation and algebraic computation (68W30)

Recommendations

• Non-commutative arithmetic circuits with division
• Non-commutative circuits and the sum-of-squares problem
• Deterministic polynomial identity testing in non-commutative models
• Operator scaling: theory and applications
• Lower bounds for arithmetic circuits via the Hankel matrix

Cites work

• (Leveled) fully homomorphic encryption without bootstrapping
• A hierarchy of polynomial time lattice basis reduction algorithms
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Bounds for Width Two Branching Programs
• Efficient Fully Homomorphic Encryption from (Standard) LWE
• Evaluating Branching Programs on Encrypted Data
• Fully homomorphic encryption using ideal lattices
• Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP
• Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based
• scientific article; zbMATH DE number 1559544 (Why is no real title available?)
• New lattice-based cryptographic constructions
• On lattices, learning with errors, random linear codes, and cryptography
• On lattices, learning with errors, random linear codes, and cryptography
• Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions
• Public-key cryptosystems from the worst-case shortest vector problem
• Toward basing fully homomorphic encryption on worst-case hardness
• Trapdoors for hard lattices and new cryptographic constructions
• Trapdoors for lattices: simpler, tighter, faster, smaller

Cited in

(13)

• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• Algorithms for orbit closure separation for invariants and semi-invariants of matrices
• Characteristic free description of semi-invariants of \(2 \times 2\) matrices
• Operator scaling: theory and applications
• Ranks of linear matrix pencils separate simultaneous similarity orbits
• Non-commutative arithmetic circuits with division
• Characterizing propositional proofs as noncommutative formulas
• On non-commutative rank and tensor rank
• Polynomial degree bounds for matrix semi-invariants
• Expressing a fraction of two determinants as a determinant
• Efficient Black-Box Identity Testing for Free Group Algebras
• Non-commutative circuits and the sum-of-squares problem
• Non-commutative circuits and the sum-of-squares problem

This page was built for publication: Non-commutative arithmetic circuits with division

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