NDLI: The Complexity of DNF of Parities

Please wait, while we are loading the content...

Can Almost Everybody be Almost Happy?

Permanent v. Determinant: An Exponential Lower Bound Assuming Symmetry

Local Algorithms for Block Models with Side Information

Strategic Classification

Obfuscating Conjunctions under Entropic Ring LWE

Timeability of Extensive-Form Games

Rational Proofs with Multiple Provers

Coordination Complexity: Small Information Coordinating Large Populations

Spectral Embedding of k-Cliques, Graph Partitioning and k-Means

How To Bootstrap Anonymous Communication

Information Complexity Density and Simulation of Protocols

Mechanisms With Costly Knowledge

On Hardness of Approximating the Parameterized Clique Problem

Distribution Design

A PAC Approach to Application-Specific Algorithm Selection

Secure Multiparty Computation with General Interaction Patterns

Auction Revenue in the General Spiteful-Utility Model

Lower Bounds: From Circuits to QBF Proof Systems

On a Natural Dynamics for Linear Programming

On Sketching Quadratic Forms

Time-Lock Puzzles from Randomized Encodings

Satisfiability on Mixed Instances

On the Computational Complexity of Optimal Simple Mechanisms

The Complexity of DNF of Parities

Sampling Correctors

An Axiomatic Approach to Community Detection

Fully Succinct Garbled RAM

How to Incentivize Data-Driven Collaboration Among Competing Parties

Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility

On the Space Complexity of Linear Programming with Preprocessing

Energy-Efficient Algorithms

Is There an Oblivious RAM Lower Bound?

On the Computational Complexity of Limit Cycles in Dynamical Systems

Smooth Boolean Functions are Easy: Efficient Algorithms for Low-Sensitivity Functions

On Being Far from Far and on Dual Problems in Property Testing: [Extended Abstract]

Cryptography for Parallel RAM from Indistinguishability Obfuscation

From Nash Equilibria to Chain Recurrent Sets: Solution Concepts and Topology

The Space "Just Above" BQP

Simultaneous Private Learning of Multiple Concepts

Weighted Gate Elimination: Boolean Dispersers for Quadratic Varieties Imply Improved Circuit Lower Bounds

The Complexity of DNF of Parities

Content Provider	ACM Digital Library
Author	Shinkar, Igor Cohen, Gil
Abstract	We study depth 3 circuits of the form OR-AND-XOR, or equivalently -- DNF of parities. This model was first explicitly studied by Jukna (CPC'06) who obtained a $2^{\{Ω(n)}$ lower bound, using graph theoretic arguments, for explicit functions. Several related models have gained attention in the last few years, such as parity decision trees, the parity kill number and AC0-XOR circuits. For a Boolean function f on the n dimensional Boolean cube, we denote by DNFParity(f) the least integer s for which there exists an OR-AND-XOR circuit, with OR gate of fan-in s, that computes f. We summarize some of our results: For any affine disperser f for dimension k, it holds that DNFParity(f) is bounded below by $2^{\{n-2k}.$ By plugging Shaltiel's affine disperser (FOCS'11) we obtain an explicit $2^{\{n-n^{o(1)}}$ lower bound. We give a non-trivial general upper bound by showing that DNFParity(f) < O(2n / n) for any function f on n bits. This bound is shown to be tight up to an O(log n) factor. We show that for any symmetric function f it holds that DNFParity(f) < 1.5n poly(n). Furthermore, there exists a symmetric function f for which this bound is tight up to a polynomial factor. For threshold functions we show tighter bounds. For example, we show that the majority function has DNFParity complexity of $2^{\{n/2}$ poly(n). This is also tight up to a polynomial factor. For the inner product function IP on n inputs we show that DNFParity(IP) = $2^{\{n/2\}-1}.$ Previously, Jukna gave a lower bound of $Ω(2^{n/4})$ for the DNFParity complexity of this function. We further give bounds for any low degree polynomial. Finally, we obtain a $2^{n-o(n)}$ average case lower bound for the parity decision tree model using affine extractors.
Starting Page	47
Ending Page	58
Page Count	12
File Format	PDF
ISBN	9781450340571
DOI	10.1145/2840728.2840734
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-01-14
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Affine disperser Affine extractors Dnf
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Simple Affine Extractors Using Dimension Expansion

A New Approach to Affine Extractors and Dispersers

Extractors for Low-Weight Affine Sources

Extractors for Circuit Sources

Attribute-Efficient and Non-adaptive Learning of Parities and DNF Expressions (2007)

Affine Dispersers from Subspace Polynomials

Affine dispersers from subspace polynomials

Linear degree extractors and the inapproximability of max clique and chromatic number

Linear Branching Programs and Directional Affine Extractors

The Complexity of DNF of Parities

Similar Documents

Simple Affine Extractors Using Dimension Expansion

A New Approach to Affine Extractors and Dispersers

Extractors for Low-Weight Affine Sources

Extractors for Circuit Sources

Attribute-Efficient and Non-adaptive Learning of Parities and DNF Expressions (2007)

Affine Dispersers from Subspace Polynomials

Affine dispersers from subspace polynomials

Linear degree extractors and the inapproximability of max clique and chromatic number

Linear Branching Programs and Directional Affine Extractors

The Complexity of DNF of Parities