Lower bounds against weakly-uniform threshold circuits
type: Item
instance of: scholarly article
title: Lower bounds against weakly-uniform threshold circuits
zbMATH Open document ID: 1314.68142
author: Ruiwen Chen
author: Valentine Kabanets
author: Jeff Kinne
published in: Algorithmica
publication date: 2015-01-19T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 6387679
zbMATH Keywords: advice complexity classes
zbMATH Keywords: alternating Turing machines
zbMATH Keywords: counting hierarchy
zbMATH Keywords: permanent
zbMATH Keywords: succinct circuits
zbMATH Keywords: threshold circuits
zbMATH Keywords: uniform circuit lower bounds
zbMATH Keywords: weakly-uniform circuits
MaRDI profile type: Publication
full work available at URL: s00453-013-9823-y
OpenAlex ID: W2078952510
cites work: FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
cites work: Q4267800
cites work: A Uniform Circuit Lower Bound for the Permanent
cites work: Computational Complexity
cites work: On ACC
cites work: Q4258566
cites work: Alternation
cites work: Lower Bounds against Weakly Uniform Circuits
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: The power of the middle bit of a \(\#\)P function
cites work: Q3942397
cites work: Nonuniform lower bounds for exponential time classes
cites work: Q4708583
cites work: Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth
cites work: Derandomizing polynomial identity tests means proving circuit lower bounds
cites work: Circuit-size lower bounds and non-reducibility to sparse sets
cites work: Turing machines that take advice
cites work: On TC0 Lower Bounds for the Permanent
cites work: Explicit lower bound of 4.5n - o(n) for boolena circuits
cites work: Q3249579
cites work: Log Space Recognition and Translation of Parenthesis Languages
cites work: Q4938667
cites work: On uniformity within \(NC^ 1\)
cites work: Parallel computation with threshold functions
cites work: Languages to diagonalize against advice classes
cites work: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
cites work: Natural proofs
cites work: On uniform circuit complexity
cites work: PP is as Hard as the Polynomial-Time Hierarchy
cites work: Complexity classes defined by counting quantifiers
cites work: The complexity of computing the permanent
cites work: The complexity of combinatorial problems with succinct input representation
cites work: A Turing machine time hierarchy
cites work: #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
DOI: 10.1007/S00453-013-9823-Y
description: scientific article; zbMATH DE number 6387679