On the public citation graph

On deterministic approximation of DNF

https://doi.org/10.1007/bf01940873

0 signed · 64 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.

Claim with ORCID

Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.

See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/bf02128670openalex-snapshot

Approximate Inclusion-Exclusion

inferredcites →https://doi.org/10.1016/0168-0072(83)90038-6openalex-snapshot

∑11-Formulae on finite structures

inferredcites →https://doi.org/10.1016/0196-6774(86)90019-2openalex-snapshot

A fast and simple randomized parallel algorithm for the maximal independent set problem

inferredcites →https://doi.org/10.1016/0196-6774(89)90038-2openalex-snapshot

Monte-Carlo approximation algorithms for enumeration problems

inferredcites →https://doi.org/10.1016/0304-3975(79)90044-6openalex-snapshot

The Complexity of Computing the Permanent

inferredcites →https://doi.org/10.1109/fscs.1990.89575openalex-snapshot

Simple construction of almost k-wise independent random variables

inferredcites →https://doi.org/10.1109/istcs.1993.253488openalex-snapshot

Deterministic approximate counting of depth-2 circuits

inferredcites →https://doi.org/10.1109/sfcs.1981.35openalex-snapshot

Parity, circuits, and the polynomial-time hierarchy

inferredcites →https://doi.org/10.1109/sfcs.1983.35openalex-snapshot

Monte-Carlo algorithms for enumeration and reliability problems

inferredcites →https://doi.org/10.1109/sfcs.1985.19openalex-snapshot

Deterministic simulation of probabilistic constant depth circuits

inferredcites →https://doi.org/10.1109/sfcs.1985.49openalex-snapshot

Separating the polynomial-time hierarchy by oracles

inferredcites →https://doi.org/10.1109/sfcs.1988.21916openalex-snapshot

Hardness vs. randomness

inferredcites →https://doi.org/10.1112/jlms/s1-35.1.85openalex-snapshot

Intersection Theorems for Systems of Sets

inferredcites →https://doi.org/10.1137/0215074openalex-snapshot

A Simple Parallel Algorithm for the Maximal Independent Set Problem

inferredcites →https://doi.org/10.1145/100216.100244openalex-snapshot

Small-bias probability spaces: efficient constructions and applications

inferredcites →https://doi.org/10.1145/12130.12132openalex-snapshot

Almost optimal lower bounds for small depth circuits

inferredcites →https://doi.org/10.1145/129712.129714openalex-snapshot

Approximations of general independent distributions

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1002/rsa.20786openalex-snapshot

On polynomial approximations to AC

inferred← citeshttps://doi.org/10.1002/rsa.20991openalex-snapshot

On the probabilistic degree of OR over the reals

inferred← citeshttps://doi.org/10.1007/978-1-4615-0013-1_18openalex-snapshot

Derandomization in Combinatorial Optimization

inferred← citeshttps://doi.org/10.1007/978-3-540-27821-4_37openalex-snapshot

A Note on Approximate Counting for k-DNF

inferred← citeshttps://doi.org/10.1007/978-3-642-15369-3_38openalex-snapshot

Improved Pseudorandom Generators for Depth 2 Circuits

inferred← citeshttps://doi.org/10.1007/bf01200907openalex-snapshot

Efficient construction of a small hitting set for combinatorial rectangles in high dimension

inferred← citeshttps://doi.org/10.1007/s00037-007-0228-7openalex-snapshot

Every Linear Threshold Function has a Low-Weight Approximator

inferred← citeshttps://doi.org/10.1007/s00037-012-0036-6openalex-snapshot

Pseudorandom Generators for Combinatorial Checkerboards

inferred← citeshttps://doi.org/10.1007/s00037-013-0068-6openalex-snapshot

DNF sparsification and a faster deterministic counting algorithm

inferred← citeshttps://doi.org/10.1007/s00440-017-0804-yopenalex-snapshot

A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting

inferred← citeshttps://doi.org/10.1007/s00778-012-0268-8openalex-snapshot

Mining frequent subgraphs over uncertain graph databases under probabilistic semantics

inferred← citeshttps://doi.org/10.1007/s10601-018-9301-xopenalex-snapshot

Not all FPRASs are equal: demystifying FPRASs for DNF-counting

inferred← citeshttps://doi.org/10.1109/ccc.2006.18openalex-snapshot

Every Linear Threshold Function has a Low-Weight Approximator

inferred← citeshttps://doi.org/10.1109/ccc.2009.35openalex-snapshot

Poly-logarithmic Independence Fools AC^0 Circuits

inferred← citeshttps://doi.org/10.1109/ccc.2012.38openalex-snapshot

DNF Sparsification and a Faster Deterministic Counting Algorithm

inferred← citeshttps://doi.org/10.1109/ccc.2014.31openalex-snapshot

Deterministic Approximate Counting for Juntas of Degree-2 Polynomial Threshold Functions

inferred← citeshttps://doi.org/10.1109/ccc.2014.33openalex-snapshot

Algorithms for Circuits and Circuits for Algorithms

inferred← citeshttps://doi.org/10.1109/focs.2007.28openalex-snapshot

Polylogarithmic Independence Can Fool DNF Formulas

inferred← citeshttps://doi.org/10.1109/focs.2007.55openalex-snapshot

Smooth Histograms for Sliding Windows

inferred← citeshttps://doi.org/10.1109/focs.2011.32openalex-snapshot

An FPTAS for #Knapsack and Related Counting Problems

inferred← citeshttps://doi.org/10.1109/focs.2017.80openalex-snapshot

Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time

inferred← citeshttps://doi.org/10.1109/focs52979.2021.00103openalex-snapshot

MAJORITY-3SAT (and Related Problems) in Polynomial Time

inferred← citeshttps://doi.org/10.1109/icde.2013.6544869openalex-snapshot

Optimizing approximations of DNF query lineage in probabilistic XML

inferred← citeshttps://doi.org/10.1109/ismvl.2009.47openalex-snapshot

Counting Problems and Clones of Functions

inferred← citeshttps://doi.org/10.1137/070691954openalex-snapshot

Polylogarithmic Independence Can Fool DNF Formulas

inferred← citeshttps://doi.org/10.1137/10080703xopenalex-snapshot

Improving Exhaustive Search Implies Superpolynomial Lower Bounds

inferred← citeshttps://doi.org/10.1137/11083976xopenalex-snapshot

A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions

inferred← citeshttps://doi.org/10.1137/s0895480100367664openalex-snapshot

Deterministic Hypergraph Coloring and Its Applications

inferred← citeshttps://doi.org/10.1145/1490270.1490273openalex-snapshot

A Simple Proof of Bazzi’s Theorem

inferred← citeshttps://doi.org/10.1145/1754399.1754401openalex-snapshot

Polylogarithmic independence fools AC 0 circuits

inferred← citeshttps://doi.org/10.1145/1804669.1804681openalex-snapshot

Probabilistic data exchange

inferred← citeshttps://doi.org/10.1145/1806689.1806723openalex-snapshot

Improving exhaustive search implies superpolynomial lower bounds

inferred← citeshttps://doi.org/10.1145/1835804.1835885openalex-snapshot

Discovering frequent subgraphs over uncertain graph databases under probabilistic semantics

inferred← citeshttps://doi.org/10.1145/1989727.1989729openalex-snapshot

Probabilistic data exchange

inferred← citeshttps://doi.org/10.1145/2591796.2591800openalex-snapshot

Efficient deterministic approximate counting for low-degree polynomial threshold functions

inferred← citeshttps://doi.org/10.1201/9781420011296.ch18openalex-snapshot

Parallel Algorithms via the Probabilistic Method

inferred← citeshttps://doi.org/10.14288/1.0043373openalex-snapshot

Deterministic Approximate Counting for Degree-2 Polynomial Threshold Functions

inferred← citeshttps://doi.org/10.1561/0400000109openalex-snapshot

Paradigms for Unconditional Pseudorandom Generators

inferred← citeshttps://doi.org/10.24963/ijcai.2023/226openalex-snapshot

Engineering an Efficient Approximate DNF-Counter

inferred← citeshttps://doi.org/10.4086/toc.2022.v018a004openalex-snapshot

inferred← citeshttps://doi.org/10.4171/022-3/54openalex-snapshot

Pseudorandomness and combinatorial constructions

inferred← citeshttps://doi.org/10.4230/lipics.approx-random.2016.32openalex-snapshot

On Polynomial Approximations to AC^0

inferred← citeshttps://doi.org/10.4230/lipics.approx-random.2018.56openalex-snapshot

Improved Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas

inferred← citeshttps://doi.org/10.4230/lipics.ccc.2017.15openalex-snapshot

Tight Bounds on the Fourier Spectrum of AC0

inferred← citeshttps://doi.org/10.4230/lipics.ccc.2018.2openalex-snapshot

A PRG for Boolean PTF of Degree 2 with Seed Length Subpolynomial in epsilon and Logarithmic in n

inferred← citeshttps://doi.org/10.48550/arxiv.1205.3534openalex-snapshot

DNF Sparsification and a Faster Deterministic Counting Algorithm

inferred← citeshttps://doi.org/10.48550/arxiv.1711.08852openalex-snapshot

Relating counting complexity to non-uniform probability measures

Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.