License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.850
URN: urn:nbn:de:0030-drops-53400
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5340/
Go to the corresponding LIPIcs Volume Portal

Guo, Siyao ; Komargodski, Ilan

Negation-Limited Formulas

pdf-format:
50.pdf (0.6 MB)

Abstract

We give an efficient structural decomposition theorem for formulas that depends on their negation complexity and demonstrate its power with the following applications.

We prove that every formula that contains t negation gates can be shrunk using a random restriction to a formula of size O(t) with the shrinkage exponent of monotone formulas. As a result, the shrinkage exponent of formulas that contain a constant number of negation gates is equal to the shrinkage exponent of monotone formulas.

We give an efficient transformation of formulas with t negation gates to circuits with log(t) negation gates. This transformation provides a generic way to cast results for negation-limited circuits to the setting of negation-limited formulas. For example, using a result of Rossman (CCC'15), we obtain an average-case lower bound for formulas of polynomial-size on n variables with n^{1/2-epsilon} negations.

In addition, we prove a lower bound on the number of negations required to compute one-way permutations by polynomial-size formulas.

BibTeX - Entry

@InProceedings{guo_et_al:LIPIcs:2015:5340,
  author =	{Siyao Guo and Ilan Komargodski},
  title =	{{Negation-Limited Formulas}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{850--866},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5340},
  URN =		{urn:nbn:de:0030-drops-53400},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.850},
  annote =	{Keywords: Negation complexity, De Morgan formulas, Shrinkage}
}

Keywords: Negation complexity, De Morgan formulas, Shrinkage
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Issue Date: 2015
Date of publication: 13.08.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI