Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > MONOTONE ARITHMETIC CIRCUITS:
Reports tagged with Monotone Arithmetic Circuits:
TR07-085 | 2nd September 2007
Ran Raz, Amir Yehudayoff

Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors

We study multilinear formulas, monotone arithmetic circuits, maximal-partition discrepancy, best-partition communication complexity and extractors constructions. We start by proving lower bounds for an explicit polynomial for the following three subclasses of syntactically multilinear arithmetic formulas over the field C and the set of variables {x1,...,xn}:

1. Noise-resistant. A syntactically multilinear ... more >>>


TR09-073 | 6th September 2009
Vikraman Arvind, Pushkar Joglekar, Srikanth Srinivasan

On Lower Bounds for Constant Width Arithmetic Circuits

The motivation for this paper is to study the complexity of constant-width arithmetic circuits. Our main results are the following.
1. For every k > 1, we provide an explicit polynomial that can be computed by a linear-sized monotone circuit of width 2k but has no subexponential-sized monotone circuit ... more >>>


TR14-080 | 11th June 2014
Stasys Jukna

Lower Bounds for Tropical Circuits and Dynamic Programs

Revisions: 1

Tropical circuits are circuits with Min and Plus, or Max and Plus operations as gates. Their importance stems from their intimate relation to dynamic programming algorithms. The power of tropical circuits lies somewhere between that of monotone boolean circuits and monotone arithmetic circuits. In this paper we present some lower ... more >>>


TR18-124 | 6th July 2018
Amir Yehudayoff

Separating Monotone VP and VNP

This work is about the monotone versions of the algebraic complexity classes VP and VNP. The main result is that monotone VNP is strictly stronger than monotone VP.

more >>>

TR20-166 | 9th November 2020
Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay

Lower Bounds for Monotone Arithmetic Circuits Via Communication Complexity

Revisions: 1

Valiant (1980) showed that general arithmetic circuits with negation can be exponentially more powerful than monotone ones. We give the first qualitative improvement to this classical result: we construct a family of polynomials $P_n$ in $n$ variables, each of its monomials has positive coefficient, such that $P_n$ can be computed ... more >>>


TR20-181 | 4th December 2020
Bruno Pasqualotto Cavalar, Mrinal Kumar, Benjamin Rossman

Monotone Circuit Lower Bounds from Robust Sunflowers

Revisions: 2

Robust sunflowers are a generalization of combinatorial sunflowers that have applications in monotone circuit complexity, DNF sparsification, randomness extractors, and recent advances on the Erd\H{o}s-Rado sunflower conjecture. The recent breakthrough of Alweiss, Lovett, Wu and Zhang gives an improved bound on the maximum size of a $w$-set system that excludes ... more >>>


TR20-191 | 27th December 2020
Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay

Negations Provide Strongly Exponential Savings

We show that there is a family of monotone multilinear polynomials over $n$ variables in VP, such that any monotone arithmetic circuit for it would be of size $2^{\Omega(n)}$. Before our result, strongly exponential lower bounds on the size of monotone circuits were known only for computing explicit polynomials in ... more >>>




ISSN 1433-8092 | Imprint