On the public citation graph
Minimizing DNF Formulas and AC^0_d Circuits Given a Truth Table
0 signed · 59 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.
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.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1006/jcss.1996.0032openalex-snapshot
Oracles and Queries That Are Sufficient for Exact Learning
inferredcites →https://doi.org/10.1006/jcss.2001.1763openalex-snapshot
Easiness Assumptions and Hardness Tests: Trading Time for Zero Error
inferredcites →https://doi.org/10.1007/3-540-60178-3_86openalex-snapshot
Some consequences of cryptographical conjectures for S 2 1 and EF
inferredcites →https://doi.org/10.1007/bf00114011openalex-snapshot
On the limits of proper learnability of subclasses of DNF formulas
inferredcites →https://doi.org/10.1007/bf01262930openalex-snapshot
Simple learning algorithms using divide and conquer
inferredcites →https://doi.org/10.1007/pl00001593openalex-snapshot
Complexity theoretic hardness results for query learning
inferredcites →https://doi.org/10.1016/0012-365x(75)90058-8openalex-snapshot
On the ratio of optimal integral and fractional covers
inferredcites →https://doi.org/10.1016/0012-365x(78)90168-1openalex-snapshot
On the number of prime implicants
inferredcites →https://doi.org/10.1016/0167-9260(94)00007-7openalex-snapshot
Two-level logic minimization: an overview
inferredcites →https://doi.org/10.1016/0304-3975(76)90061-xopenalex-snapshot
The polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/j.jcss.2004.10.001openalex-snapshot
Exact learning of DNF formulas using DNF hypotheses
inferredcites →https://doi.org/10.1016/s0020-0190(97)00026-4openalex-snapshot
A simple algorithm for learning O(log n)-term DNF
inferredcites →https://doi.org/10.1016/s0022-0000(74)80044-9openalex-snapshot
Approximation algorithms for combinatorial problems
inferredcites →https://doi.org/10.1016/s1571-0661(04)00301-9openalex-snapshot
Parameterized Complexity
inferredcites →https://doi.org/10.1109/ccc.2000.856746openalex-snapshot
Easiness assumptions and hardness tests: trading time for zero error
inferredcites →https://doi.org/10.1109/ccc.2001.933896openalex-snapshot
Time-space tradeoffs in the counting hierarchy
inferredcites →https://doi.org/10.1109/ccc.2003.1214421openalex-snapshot
Derandomization and distinguishing complexity
inferredcites →https://doi.org/10.1109/focs.2004.36openalex-snapshot
Learnability and Automatizability
inferredcites →https://doi.org/10.1109/sfcs.1998.743506openalex-snapshot
The minimum equivalent DNF problem and shortest implicants
inferredcites →https://doi.org/10.1109/sffcs.1999.814619openalex-snapshot
Hardness of approximating Σ/sub 2//sup p/ minimization problems
inferredcites →https://doi.org/10.1109/tcad.2005.855944openalex-snapshot
Complexity of two-level logic minimization
inferredcites →https://doi.org/10.1137/0211045openalex-snapshot
Approximation Algorithms for the Set Covering and Vertex Cover Problems
inferredcites →https://doi.org/10.1137/s0097539704443057openalex-snapshot
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
inferredcites →https://doi.org/10.1137/s0097539795280895openalex-snapshot
A Parallel Repetition Theorem
inferredcites →https://doi.org/10.1145/1150334.1150336openalex-snapshot
Algorithmic construction of sets for k -restrictions
inferredcites →https://doi.org/10.1145/168304.168309openalex-snapshot
Linear time deterministic learning of k -term DNF
inferredcites →https://doi.org/10.1145/174644.174647openalex-snapshot
Cryptographic Limitations on Learning Boolean Formulae and Finite Automata
inferredcites →https://doi.org/10.1145/180139.181063openalex-snapshot
On the limits of proper learnability of subclasses of DNF formulas
inferredcites →https://doi.org/10.1145/185675.306789openalex-snapshot
On the hardness of approximating minimization problems
inferredcites →https://doi.org/10.1145/258533.258599openalex-snapshot
Approximation of k -set cover by semi-local optimization
inferredcites →https://doi.org/10.1145/285055.285059openalex-snapshot
A threshold of ln n for approximating set cover
inferredcites →https://doi.org/10.1145/380752.380839openalex-snapshot
Non-approximability results for optimization problems on bounded degree instances
inferredcites →https://doi.org/10.1145/48014.63140openalex-snapshot
Computational limitations on learning from examples
inferredcites →https://doi.org/10.1145/73007.73049openalex-snapshot
Crytographic limitations on learning Boolean formulae and finite automata
inferredcites →https://doi.org/10.1287/moor.4.3.233openalex-snapshot
A Greedy Heuristic for the Set-Covering Problem
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1007/978-3-540-70575-8_4openalex-snapshot
Optimal Cryptographic Hardness of Learning Monotone Functions
inferred← citeshttps://doi.org/10.1007/s00453-007-9039-0openalex-snapshot
Approximability of Minimum AND-Circuits
inferred← citeshttps://doi.org/10.1016/j.dam.2011.05.013openalex-snapshot
Boolean functions with a simple certificate for CNF complexity
inferred← citeshttps://doi.org/10.1016/j.ipl.2013.07.001openalex-snapshot
Boolean functions with long prime implicants
inferred← citeshttps://doi.org/10.1016/j.jcss.2008.07.007openalex-snapshot
Hardness of approximate two-level logic minimization and PAC learning with membership queries
inferred← citeshttps://doi.org/10.1109/focs.2008.37openalex-snapshot
Hardness of Minimizing and Learning DNF Expressions
inferred← citeshttps://doi.org/10.1109/focs46700.2020.00047openalex-snapshot
Constant Depth Formula and Partial Function Versions of MCSP are Hard
inferred← citeshttps://doi.org/10.1109/focs52979.2021.00050openalex-snapshot
The Minimum Formula Size Problem is (ETH) Hard
inferred← citeshttps://doi.org/10.1109/icnp.2016.7784452openalex-snapshot
FIB efficiency in distributed platforms
inferred← citeshttps://doi.org/10.1109/tnet.2015.2407831openalex-snapshot
Exploiting Order Independence for Scalable and Expressive Packet Classification
inferred← citeshttps://doi.org/10.1109/tnet.2017.2728642openalex-snapshot
Efficient FIB Representations on Distributed Platforms
inferred← citeshttps://doi.org/10.1137/20m1383562openalex-snapshot
Constant Depth Formula and Partial Function Versions of MCSP Are Hard
inferred← citeshttps://doi.org/10.1145/2491185.2491219openalex-snapshot
Towards efficient implementation of packet classifiers in SDN/OpenFlow
inferred← citeshttps://doi.org/10.1145/2619239.2626294openalex-snapshot
SAX-PAC (Scalable And eXpressive PAcket Classification)
inferred← citeshttps://doi.org/10.1145/2740070.2626294openalex-snapshot
SAX-PAC (Scalable And eXpressive PAcket Classification)
inferred← citeshttps://doi.org/10.1145/3078861.3078865openalex-snapshot
Attribute Expressions, Policy Tables and Attribute-Based Access Control
inferred← citeshttps://doi.org/10.48550/arxiv.1404.0703openalex-snapshot
Joins via Geometric Resolutions: Worst-case and Beyond
inferred← citeshttps://doi.org/10.7916/d8w66sm1openalex-snapshot
On the Learnability of Monotone Functions
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.