Randomized feasible interpolation and monotone circuits with a local oracle
type: Item
instance of: scholarly article
title: Randomized feasible interpolation and monotone circuits with a local oracle
DOI: 10.1142/S0219061318500125
author: Jan Krajíček
published in: Journal of Mathematical Logic
publication date: 2018-12-20T00:00:00Z
full work available at URL: https://arxiv.org/abs/1611.08680
Mathematics Subject Classification ID: 03-XX
zbMATH DE Number: 6996246
zbMATH Keywords: proof complexity
zbMATH Keywords: communication complexity
zbMATH Keywords: resolution
zbMATH Keywords: feasible interpolation
zbMATH Keywords: monotone circuits
MaRDI profile type: Publication
cites work: Pseudorandom Generators in Propositional Proof Complexity
cites work: The monotone circuit complexity of Boolean functions
cites work: Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
cites work: Fragments of approximate counting
cites work: Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
cites work: Q4228469
cites work: Several notes on the power of Gomory-Chvátal cuts
cites work: Lower Bounds for Splittings by Linear Combinations
cites work: Improved Lower Bounds for Tree-Like Resolution over Linear Inequalities
cites work: Q4856172
cites work: Q4699287
cites work: Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
cites work: Discretely ordered modules as a first-order extension of the cutting planes proof system
cites work: Interpolation by a Game
cites work: On the weak pigeonhole principle
cites work: On monotone circuits with local oracles and clique lower bounds
cites work: Q4284623
cites work: Lower bounds for resolution and cutting plane proofs and monotone computations
cites work: Q4215637
cites work: A tradeoff between length and width in resolution
cites work: Resolution over linear equations and multilinear proofs
cites work: Monotone circuits for matching require linear depth
cites work: Q3758729
cites work: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
cites work: Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
cites work: Lower bounds for the polynomial calculus
OpenAlex ID: W3098043201
Wikidata QID: Q129592975
description: scientific article; zbMATH DE number 6996246