On the public citation graph
Parity, circuits, and the polynomial-time hierarchy
0 signed · 872 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.1007/bf01405045openalex-snapshot
Complexity of the realization of a linear function in the class of II-circuits
inferredcites →https://doi.org/10.1007/bf01683260openalex-snapshot
Relativization of questions about log space computability
inferredcites →https://doi.org/10.1007/bf01747074openalex-snapshot
Method of determining lower bounds for the complexity of P-schemes
inferredcites →https://doi.org/10.1016/0304-3975(76)90061-xopenalex-snapshot
The polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/0304-3975(79)90043-4openalex-snapshot
A second step toward the polynomial hierarchy
inferredcites →https://doi.org/10.1016/0304-3975(80)90027-4openalex-snapshot
On counting problems and the polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/0304-3975(80)90074-2openalex-snapshot
A 3n-lower bound on the network complexity of Boolean functions
inferredcites →https://doi.org/10.1016/0378-4754(79)90115-0openalex-snapshot
The complexity of computing
inferredcites →https://doi.org/10.1049/ip-i-1.1981.0010openalex-snapshot
Introduction to V.L.S.I. Systems
inferredcites →https://doi.org/10.1109/sfcs.1981.3openalex-snapshot
A complexity theory based on Boolean algebra
inferredcites →https://doi.org/10.1109/sfcs.1981.35openalex-snapshot
Parity, circuits, and the polynomial-time hierarchy
inferredcites →https://doi.org/10.1137/0204037openalex-snapshot
Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
inferredcites →https://doi.org/10.1137/0206030openalex-snapshot
A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
inferredcites →https://doi.org/10.1145/800116.803750openalex-snapshot
A 2.5 n-lower bound on the combinational complexity of Boolean functions
inferredcites →https://doi.org/10.1145/800125.804029openalex-snapshot
Word problems requiring exponential time(Preliminary Report)
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1002/malq.19970430313openalex-snapshot
Forcing in Finite Structures
inferred← citeshttps://doi.org/10.1002/malq.19990450411openalex-snapshot
Definability of Geometric Properties in Algebraically Closed Fields
inferred← citeshttps://doi.org/10.1002/malq.200310041openalex-snapshot
Arithmetical definability over finite structures
inferred← citeshttps://doi.org/10.1002/malq.201200055openalex-snapshot
Iteration on notation and unary functions
inferred← citeshttps://doi.org/10.1002/malq.202200068openalex-snapshot
Borel complexity and Ramsey largeness of sets of oracles separating complexity classes
inferred← citeshttps://doi.org/10.1006/inco.1994.1054openalex-snapshot
Exponential Size Lower Bounds for Some Depth 3 Circuits
inferred← citeshttps://doi.org/10.1006/inco.1994.1057openalex-snapshot
Depth Reduction for Circuits of Unbounded Fan-in
inferred← citeshttps://doi.org/10.1006/inco.1994.1059openalex-snapshot
Approximating Threshold Circuits by Rational Functions
inferred← citeshttps://doi.org/10.1006/inco.1995.1067openalex-snapshot
Regular Languages Defined with Generalized Quantifiers
inferred← citeshttps://doi.org/10.1006/inco.1996.0043openalex-snapshot
Sensitive Functions and Approximate Problems
inferred← citeshttps://doi.org/10.1006/inco.1996.0071openalex-snapshot
Logspace and Logtime Leaf Languages
inferred← citeshttps://doi.org/10.1006/inco.1997.2646openalex-snapshot
A Tight Relationship between Generic Oracles and Type-2 Complexity Theory
inferred← citeshttps://doi.org/10.1006/inco.1998.2702openalex-snapshot
A Constant-Space Sequential Model of Computation for First-Order Logic
inferred← citeshttps://doi.org/10.1006/inco.1998.2732openalex-snapshot
Threshold Circuits of Small Majority-Depth
inferred← citeshttps://doi.org/10.1006/inco.1999.2810openalex-snapshot
Tally NP Sets and Easy Census Functions
inferred← citeshttps://doi.org/10.1006/inco.1999.2842openalex-snapshot
Counting Modulo Quantifiers on Finite Structures
inferred← citeshttps://doi.org/10.1006/inco.2000.2923openalex-snapshot
Languages Defined with Modular Counting Quantifiers
inferred← citeshttps://doi.org/10.1006/inco.2000.3017openalex-snapshot
Circuit and Decision Tree Complexity of Some Number Theoretic Problems
inferred← citeshttps://doi.org/10.1006/jcss.1996.0042openalex-snapshot
Towards Tractable Algebras for Bags
inferred← citeshttps://doi.org/10.1006/jcss.1996.0059openalex-snapshot
On Closure Properties of #P in the Context of PF∘#P
inferred← citeshttps://doi.org/10.1006/jcss.1996.0068openalex-snapshot
On the Isomorphism Conjecture for Weak Reducibilities
inferred← citeshttps://doi.org/10.1006/jcss.1997.1485openalex-snapshot
Counting Quantifiers, Successor Relations, and Logarithmic Space
inferred← citeshttps://doi.org/10.1006/jcss.1997.1520openalex-snapshot
Dyn-FO: A Parallel, Dynamic Complexity Class
inferred← citeshttps://doi.org/10.1006/jcss.1997.1524openalex-snapshot
Finitely Representable Databases
inferred← citeshttps://doi.org/10.1006/jcss.1997.1552openalex-snapshot
A Lower Bound for Perceptrons and an Oracle Separation of the PPPHHierarchy
inferred← citeshttps://doi.org/10.1006/jcss.1998.1571openalex-snapshot
Attribute-Efficient Learning in Query and Mistake-Bound Models
inferred← citeshttps://doi.org/10.1006/jcss.1998.1583openalex-snapshot
Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem
inferred← citeshttps://doi.org/10.1006/jcss.1999.1673openalex-snapshot
Circuits and Expressions with Nonassociative Gates
inferred← citeshttps://doi.org/10.1006/jcss.2000.1742openalex-snapshot
The Descriptive Complexity Approach to LOGCFL
inferred← citeshttps://doi.org/10.1006/jcss.2001.1764openalex-snapshot
On the Complexity of Some Problems on Groups Input as Multiplication Tables
inferred← citeshttps://doi.org/10.1006/jcss.2001.1774openalex-snapshot
Which Problems Have Strongly Exponential Complexity?
inferred← citeshttps://doi.org/10.1007/10703163_10openalex-snapshot
Invariant Definability and P/poly
inferred← citeshttps://doi.org/10.1007/11505877_6openalex-snapshot
Inexpressibility Results for Regular Languages in Nonregular Settings
inferred← citeshttps://doi.org/10.1007/11523468_80openalex-snapshot
Lower Bounds for Circuits with Few Modular and Symmetric Gates
inferred← citeshttps://doi.org/10.1007/11537311_12openalex-snapshot
On the Power of Unambiguity in Alternating Machines
inferred← citeshttps://doi.org/10.1007/11537311_5openalex-snapshot
Bounds on the Power of Constant-Depth Quantum Circuits
inferred← citeshttps://doi.org/10.1007/11590156_2openalex-snapshot
Computational Complexity Since 1980
inferred← citeshttps://doi.org/10.1007/11602613_78openalex-snapshot
Upper Bounds on the Computational Power of an Optical Model of Computation
inferred← citeshttps://doi.org/10.1007/11672142_55openalex-snapshot
Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two
inferred← citeshttps://doi.org/10.1007/11681878_24openalex-snapshot
On the Complexity of Parallel Hardness Amplification for One-Way Functions
inferred← citeshttps://doi.org/10.1007/11821069_34openalex-snapshot
On the Correlation Between Parity and Modular Polynomials
inferred← citeshttps://doi.org/10.1007/11830924_37openalex-snapshot
Randomness-Efficient Sampling Within NC 1
inferred← citeshttps://doi.org/10.1007/11916277_7openalex-snapshot
A Characterization of Alternating Log Time by First Order Functional Programs
inferred← citeshttps://doi.org/10.1007/3-540-12689-9_95openalex-snapshot
The classification of problems which have fast parallel algorithms
inferred← citeshttps://doi.org/10.1007/3-540-13345-3_2openalex-snapshot
The VLSI revolution in theoretical circles
inferred← citeshttps://doi.org/10.1007/3-540-16486-3_102openalex-snapshot
A depth-size tradeoff for boolean circuits with unbounded fan-in
inferred← citeshttps://doi.org/10.1007/3-540-16486-3_105openalex-snapshot
Parallel computation with threshold functions
inferred← citeshttps://doi.org/10.1007/3-540-16486-3_89openalex-snapshot
One-way functions and circuit complexity
inferred← citeshttps://doi.org/10.1007/3-540-17660-8_43openalex-snapshot
On the complexity of branching programs and decision trees for clique functions
inferred← citeshttps://doi.org/10.1007/3-540-18088-5_13openalex-snapshot
Non-uniform automata over groups
inferred← citeshttps://doi.org/10.1007/3-540-18740-5_81openalex-snapshot
The parallel complexity of some arithmetic and algebraic operations
inferred← citeshttps://doi.org/10.1007/3-540-19488-6_142openalex-snapshot
Regular languages defined with generalized quantifiers
inferred← citeshttps://doi.org/10.1007/3-540-28520-2_6openalex-snapshot
Randomized Algorithms and Complexity Classes
inferred← citeshttps://doi.org/10.1007/3-540-28520-2_8openalex-snapshot
Other Public-Key Cryptosystems and Protocols
inferred← citeshttps://doi.org/10.1007/3-540-32743-6_8openalex-snapshot
Von der Turingmaschine zum Quantencomputer — ein Gang durch die Geschichte der Komplexitätstheorie
inferred← citeshttps://doi.org/10.1007/3-540-44612-5_46openalex-snapshot
The Infinite Versions of LogSpace ≠ P Are Consistent with the Axioms of Set Theory
inferred← citeshttps://doi.org/10.1007/3-540-44666-4_28openalex-snapshot
On the Derandomization of Constant Depth Circuits
inferred← citeshttps://doi.org/10.1007/3-540-45294-x_7openalex-snapshot
The First-Order Isomorphism Theorem
inferred← citeshttps://doi.org/10.1007/3-540-45523-x_9openalex-snapshot
On Multisets in Database Systems
inferred← citeshttps://doi.org/10.1007/3-540-45655-4_59openalex-snapshot
On Reachability in Graphs with Bounded Independence Number
inferred← citeshttps://doi.org/10.1007/3-540-46583-9_5openalex-snapshot
A Generalized Quantifier Concept in Computational Complexity Theory
inferred← citeshttps://doi.org/10.1007/3-540-48238-5_15openalex-snapshot
Compilation Schemes: A Theoretical Tool for Assessing the Expressive Power of Planning Formalisms
inferred← citeshttps://doi.org/10.1007/3-540-49116-3_4openalex-snapshot
Circuit Complexity of Testing Square-Free Numbers
inferred← citeshttps://doi.org/10.1007/3-540-52921-7_54openalex-snapshot
Oracles versus proof techniques that do not relativize
inferred← citeshttps://doi.org/10.1007/3-540-54458-5_67openalex-snapshot
Some notes on threshold circuits, and multiplication in depth 4
inferred← citeshttps://doi.org/10.1007/3-540-55719-9_60openalex-snapshot
Circuit complexity and the expressive power of generalized first-order formulas
inferred← citeshttps://doi.org/10.1007/3-540-55719-9_73openalex-snapshot
UP and the low and high hierarchies: A relativized separation
inferred← citeshttps://doi.org/10.1007/3-540-55808-x_10openalex-snapshot
The complexity of graph connectivity
inferred← citeshttps://doi.org/10.1007/3-540-55808-x_5openalex-snapshot
Neural networks and complexity theory
inferred← citeshttps://doi.org/10.1007/3-540-56279-6_94openalex-snapshot
On probabilistic ACC circuits with an exact-threshold output gate
inferred← citeshttps://doi.org/10.1007/3-540-56503-5_19openalex-snapshot
A first-order isomorphism theorem
inferred← citeshttps://doi.org/10.1007/3-540-56503-5_53openalex-snapshot
Computing symmetric functions with AND/OR circuits and a single MAJORITY gate
inferred← citeshttps://doi.org/10.1007/3-540-57785-8_150openalex-snapshot
On adaptive dlogtime and polylogtime reductions
inferred← citeshttps://doi.org/10.1007/3-540-58715-2_130openalex-snapshot
My favorite ten complexity theorems of the past decade
inferred← citeshttps://doi.org/10.1007/3-540-59175-3_81openalex-snapshot
Lower bounds for modular counting by circuits with modular gates
inferred← citeshttps://doi.org/10.1007/3-540-60178-3_81openalex-snapshot
Computation models and function algebras
inferred← citeshttps://doi.org/10.1007/3-540-60178-3_96openalex-snapshot
Linear constraint query languages expressive power and complexity
inferred← citeshttps://doi.org/10.1007/3-540-60178-3_97openalex-snapshot
A constant-space sequential model of computation for first-order logic
inferred← citeshttps://doi.org/10.1007/3-540-60299-2_8openalex-snapshot
First-order definability over constraint databases
inferred← citeshttps://doi.org/10.1007/3-540-61332-3_145openalex-snapshot
A note on uniform circuit lower bounds for the counting hierarchy (extended abstract)
inferred← citeshttps://doi.org/10.1007/3-540-61550-4_149openalex-snapshot
On the query complexity of sets
inferred← citeshttps://doi.org/10.1007/3-540-62034-6_33openalex-snapshot
Circuit complexity before the dawn of the new millennium
inferred← citeshttps://doi.org/10.1007/3-540-62592-5_77openalex-snapshot
On the complexity of balanced Boolean functions
inferred← citeshttps://doi.org/10.1007/3-540-63255-7_3openalex-snapshot
Nonmonotonic reasoning with quantified boolean constraints
inferred← citeshttps://doi.org/10.1007/3-540-63307-3_80openalex-snapshot
Trans-dichotomous algorithms without multiplication — some upper and lower bounds
inferred← citeshttps://doi.org/10.1007/3-540-68535-9_20openalex-snapshot
An Exact Characterization of Symmetric Functions in qAC0[2]
inferred← citeshttps://doi.org/10.1007/3-540-68535-9_38openalex-snapshot
Combinatorial Properties of Classes of Functions Hard to Compute in Constant Depth
inferred← citeshttps://doi.org/10.1007/3-540-68804-8openalex-snapshot
Finite Model Theory and Its Applications
inferred← citeshttps://doi.org/10.1007/3-540-68804-8_5openalex-snapshot
Embedded Finite Models and Constraint Databases
inferred← citeshttps://doi.org/10.1007/978-0-387-30162-4_309openalex-snapshot
Quantum Algorithm for the Parity Problem
inferred← citeshttps://doi.org/10.1007/978-1-4419-6984-2_5openalex-snapshot
Model Checking Logics of Strategic Ability: Complexity*
inferred← citeshttps://doi.org/10.1007/978-1-4471-0313-4_20openalex-snapshot
Quantum Computation Relative to Oracles
inferred← citeshttps://doi.org/10.1007/978-1-4612-1388-8_15openalex-snapshot
When Can One Finite Monoid Simulate Another
inferred← citeshttps://doi.org/10.1007/978-1-4612-1872-2_11openalex-snapshot
Polynomials and Combinatorial Definitions of Languages
inferred← citeshttps://doi.org/10.1007/978-1-4612-2566-9_1openalex-snapshot
On the Existence of modulo p Cardinality Functions
inferred← citeshttps://doi.org/10.1007/978-1-4612-2566-9_10openalex-snapshot
On Frege and Extended Frege Proof Systems
inferred← citeshttps://doi.org/10.1007/978-1-4612-2566-9_12openalex-snapshot
Bounded Arithmetic and Lower Bounds in Boolean Complexity
inferred← citeshttps://doi.org/10.1007/978-1-4613-0897-3_20openalex-snapshot
Projection Complete Graph Problems Corresponding to a Branching-Program-Based Characterization of the Complexity Classes NC 1 ,Land NL
inferred← citeshttps://doi.org/10.1007/978-1-4613-3394-4_14openalex-snapshot
Measure One Results in Computational Complexity Theory
inferred← citeshttps://doi.org/10.1007/978-1-4615-1567-8_20openalex-snapshot
On the Expressive Power of Planning Formalisms
inferred← citeshttps://doi.org/10.1007/978-1-4615-2696-4_11openalex-snapshot
Learning Boolean Functions via the Fourier Transform
inferred← citeshttps://doi.org/10.1007/978-1-4615-2696-4_3openalex-snapshot
Communication Complexity and Lower Bounds for Threshold Circuits
inferred← citeshttps://doi.org/10.1007/978-1-4615-3422-8_30openalex-snapshot
The Complexity of Algorithmic Problems on Succinct Instances
inferred← citeshttps://doi.org/10.1007/978-1-4899-2608-1_18openalex-snapshot
Programs over Finite Semigroups: An Introduction
inferred← citeshttps://doi.org/10.1007/978-1-4939-2864-4_309openalex-snapshot
Quantum Algorithm for the Parity Problem
inferred← citeshttps://doi.org/10.1007/978-3-030-00111-7_32openalex-snapshot
Bounded-Memory Stream Processing
inferred← citeshttps://doi.org/10.1007/978-3-030-06170-8_2openalex-snapshot
Theoretical Computer Science: Computational Complexity
inferred← citeshttps://doi.org/10.1007/978-3-030-12797-8_2openalex-snapshot
Time and Space Complexity of P Systems — And Why They Matter
inferred← citeshttps://doi.org/10.1007/978-3-030-18126-0_12openalex-snapshot
The Inapproximability of k-DominatingSet for Parameterized $$\mathsf {{AC}^0}$$ Circuits
inferred← citeshttps://doi.org/10.1007/978-3-030-19955-5_2openalex-snapshot
The Non-hardness of Approximating Circuit Size
inferred← citeshttps://doi.org/10.1007/978-3-030-26176-4_39openalex-snapshot
LIKE Patterns and Complexity
inferred← citeshttps://doi.org/10.1007/978-3-030-40608-0_22openalex-snapshot
The Power of Programs over Monoids in J
inferred← citeshttps://doi.org/10.1007/978-3-030-43662-9_6openalex-snapshot
On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions
inferred← citeshttps://doi.org/10.1007/978-3-030-48006-6_5openalex-snapshot
Parameterized Parallel Computing and First-Order Logic
inferred← citeshttps://doi.org/10.1007/978-3-030-48516-0_19openalex-snapshot
Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata
inferred← citeshttps://doi.org/10.1007/978-3-030-48516-0_6openalex-snapshot
On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection
inferred← citeshttps://doi.org/10.1007/978-3-030-57484-0_1openalex-snapshot
Introduction to Channel Coding
inferred← citeshttps://doi.org/10.1007/978-3-030-57484-0_2openalex-snapshot
Automatic Repeat Request (ARQ)
inferred← citeshttps://doi.org/10.1007/978-3-030-57977-7_3openalex-snapshot
Query Answering in Fuzzy DL-Lite with Graded Axioms
inferred← citeshttps://doi.org/10.1007/978-3-030-60067-9_5openalex-snapshot
Temporal Ontology-Mediated Queries and First-Order Rewritability: A Short Course
inferred← citeshttps://doi.org/10.1007/978-3-030-66515-9_6openalex-snapshot
Black-Box and Data-Driven Computation
inferred← citeshttps://doi.org/10.1007/978-3-030-79416-3_15openalex-snapshot
Upper Bound for Torus Polynomials
inferred← citeshttps://doi.org/10.1007/978-3-030-80223-3_8openalex-snapshot
Hardness and Optimality in QBF Proof Systems Modulo NP
inferred← citeshttps://doi.org/10.1007/978-3-030-84259-8_17openalex-snapshot
Low-Complexity Weak Pseudorandom Functions in $$\mathtt {AC}0[\mathtt {MOD}2]$$
inferred← citeshttps://doi.org/10.1007/978-3-030-88853-4_2openalex-snapshot
A Logical Characterization of Constant-Depth Circuits over the Reals
inferred← citeshttps://doi.org/10.1007/978-3-031-28073-3_23openalex-snapshot
The P vs. NP Problem and Attempts to Settle It via Perfect Graphs State-of-the-Art Approach
inferred← citeshttps://doi.org/10.1007/978-3-031-64381-1_7openalex-snapshot
Reducing Garbled Circuit Size While Preserving Circuit Gate Privacy
inferred← citeshttps://doi.org/10.1007/978-3-031-84740-0_14openalex-snapshot
Circuit Complexity and Unambiguity
inferred← citeshttps://doi.org/10.1007/978-3-032-01907-3_16openalex-snapshot
How to Share an NP Statement or Combiners for Zero-Knowledge Proofs
inferred← citeshttps://doi.org/10.1007/978-3-032-22469-9_11openalex-snapshot
Parallel Complexity of Identifying Groups and Quasigroups via Decompositions
inferred← citeshttps://doi.org/10.1007/978-3-319-00119-7_5openalex-snapshot
The Complexity of Computations
inferred← citeshttps://doi.org/10.1007/978-3-319-03780-6_28openalex-snapshot
Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization Problems
inferred← citeshttps://doi.org/10.1007/978-3-319-05446-9_2openalex-snapshot
Investigations Concerning the Structure of Complete Sets
inferred← citeshttps://doi.org/10.1007/978-3-319-07248-7_2openalex-snapshot
On the Succinctness of Closure Operator Representations
inferred← citeshttps://doi.org/10.1007/978-3-319-15579-1_36openalex-snapshot
A Nonuniform Circuit Class with Multilayer of Threshold Gates Having Super Quasi Polynomial Size Lower Bounds Against NEXP
inferred← citeshttps://doi.org/10.1007/978-3-319-21170-1_1openalex-snapshot
Introduction to Channel Coding
inferred← citeshttps://doi.org/10.1007/978-3-319-21170-1_2openalex-snapshot
Automatic Repeat Request (ARQ)
inferred← citeshttps://doi.org/10.1007/978-3-319-21500-6_27openalex-snapshot
On Distinguishing NC $$^1$$ and NL
inferred← citeshttps://doi.org/10.1007/978-3-319-32162-2_1openalex-snapshot
$$P\mathop{ =}\limits^{?}NP$$
inferred← citeshttps://doi.org/10.1007/978-3-319-43669-2_10openalex-snapshot
Complexity Barriers as Independence
inferred← citeshttps://doi.org/10.1007/978-3-319-57048-8_3openalex-snapshot
Pseudorandom Functions: Three Decades Later
inferred← citeshttps://doi.org/10.1007/978-3-319-58747-9_21openalex-snapshot
On Algorithmic Statistics for Space-Bounded Algorithms
inferred← citeshttps://doi.org/10.1007/978-3-319-77404-6_24openalex-snapshot
An Average-Case Lower Bound Against $$\mathsf {ACC}^0$$
inferred← citeshttps://doi.org/10.1007/978-3-322-90191-0_1openalex-snapshot
Mathematik und Informatik
inferred← citeshttps://doi.org/10.1007/978-3-322-95375-9_1openalex-snapshot
Mathematik und Informatik
inferred← citeshttps://doi.org/10.1007/978-3-540-24587-2_11openalex-snapshot
The Intractability of Computing the Hamming Distance
inferred← citeshttps://doi.org/10.1007/978-3-540-24749-4_29openalex-snapshot
A Logspace Approximation Scheme for the Shortest Path Problem for Graphs with Bounded Independence Number
inferred← citeshttps://doi.org/10.1007/978-3-540-27821-4_14openalex-snapshot
Approximating Max k CSP Using Random Restrictions
inferred← citeshttps://doi.org/10.1007/978-3-540-28629-5_24openalex-snapshot
Some Meet-in-the-Middle Circuit Lower Bounds
inferred← citeshttps://doi.org/10.1007/978-3-540-31834-7_17openalex-snapshot
Hierarchies of DLOGTIME-Uniform Circuits
inferred← citeshttps://doi.org/10.1007/978-3-540-72504-6_2openalex-snapshot
Generalizations of the Compactness Theorem and Gödel’s Completeness Theorem for Nonstandard Finite Structures
inferred← citeshttps://doi.org/10.1007/978-3-540-73001-9_44openalex-snapshot
Circuit Complexity of Regular Languages
inferred← citeshttps://doi.org/10.1007/978-3-540-73420-8_19openalex-snapshot
Approximation by DNF: Examples and Counterexamples
inferred← citeshttps://doi.org/10.1007/978-3-540-73420-8_25openalex-snapshot
Universal Algebra and Hardness Results for Constraint Satisfaction Problems
inferred← citeshttps://doi.org/10.1007/978-3-540-73545-8_44openalex-snapshot
Computing Symmetric Boolean Functions by Circuits with Few Exact Threshold Gates
inferred← citeshttps://doi.org/10.1007/978-3-540-73545-8_46openalex-snapshot
“Resistant” Polynomials and Stronger Lower Bounds for Depth-Three Arithmetical Formulas
inferred← citeshttps://doi.org/10.1007/978-3-540-74208-1_33openalex-snapshot
Lower Bounds for Swapping Arthur and Merlin
inferred← citeshttps://doi.org/10.1007/978-3-540-74240-1_35openalex-snapshot
Impossibility Results on Weakly Black-Box Hardness Amplification
inferred← citeshttps://doi.org/10.1007/978-3-540-79228-4_8openalex-snapshot
Indistinguishability and First-Order Logic
inferred← citeshttps://doi.org/10.1007/978-3-540-79709-8_2openalex-snapshot
Cracks in the Defenses: Scouting Out Approaches on Circuit Lower Bounds
inferred← citeshttps://doi.org/10.1007/978-3-540-85194-3_14openalex-snapshot
A Characterisation of NL Using Membrane Systems without Charges and Dissolution
inferred← citeshttps://doi.org/10.1007/978-3-540-92800-3_5openalex-snapshot
Dualities for Constraint Satisfaction Problems
inferred← citeshttps://doi.org/10.1007/978-3-642-00982-2_3openalex-snapshot
Descriptional and Computational Complexity of Finite Automata
inferred← citeshttps://doi.org/10.1007/978-3-642-02261-6_28openalex-snapshot
Ehrenfeucht-Fraïssé Games on Random Structures
inferred← citeshttps://doi.org/10.1007/978-3-642-02927-1_12openalex-snapshot
Towards a Study of Low-Complexity Graphs
inferred← citeshttps://doi.org/10.1007/978-3-642-13089-2_16openalex-snapshot
On the Expressive Power of FO[ + ]
inferred← citeshttps://doi.org/10.1007/978-3-642-13190-5_7openalex-snapshot
Protecting Circuits from Leakage: the Computationally-Bounded and Noisy Cases
inferred← citeshttps://doi.org/10.1007/978-3-642-14165-2_10openalex-snapshot
Mean-Payoff Games and Propositional Proofs
inferred← citeshttps://doi.org/10.1007/978-3-642-18073-6_9openalex-snapshot
The Polynomial Degree of Recursive Fourier Sampling
inferred← citeshttps://doi.org/10.1007/978-3-642-20920-8_20openalex-snapshot
Characterizing Definability of Second-Order Generalized Quantifiers
inferred← citeshttps://doi.org/10.1007/978-3-642-22012-8_29openalex-snapshot
Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates
inferred← citeshttps://doi.org/10.1007/978-3-642-22993-0_40openalex-snapshot
Symmetric Functions Capture General Functions
inferred← citeshttps://doi.org/10.1007/978-3-642-24508-4openalex-snapshot
Boolean Function Complexity: Advances and Frontiers
inferred← citeshttps://doi.org/10.1007/978-3-642-27848-8_309-2openalex-snapshot
Quantum Algorithm for the Parity Problem
inferred← citeshttps://doi.org/10.1007/978-3-642-31265-6_7openalex-snapshot
Constant-Time Word-Size String Matching
inferred← citeshttps://doi.org/10.1007/978-3-642-31485-8_6openalex-snapshot
Specification and Verification of Multi-Agent Systems
inferred← citeshttps://doi.org/10.1007/978-3-642-32241-9_35openalex-snapshot
Lower Bounds against Weakly Uniform Circuits
inferred← citeshttps://doi.org/10.1007/978-3-642-32241-9_36openalex-snapshot
On TC0 Lower Bounds for the Permanent
inferred← citeshttps://doi.org/10.1007/978-3-642-40313-2_52openalex-snapshot
Small Depth Proof Systems
inferred← citeshttps://doi.org/10.1007/978-3-642-45278-9_34openalex-snapshot
Circuit Complexity of Shuffle
inferred← citeshttps://doi.org/10.1007/978-3-642-60322-8_12openalex-snapshot
Lower Bounds for the Parity Function
inferred← citeshttps://doi.org/10.1007/978-3-662-04031-7_3openalex-snapshot
Expressive Power: The Finite Case
inferred← citeshttps://doi.org/10.1007/978-3-662-04031-7_4openalex-snapshot
Expressive Power: The Infinite Case
inferred← citeshttps://doi.org/10.1007/978-3-662-07003-1_6openalex-snapshot
Complexity of First-Order Logic
inferred← citeshttps://doi.org/10.1007/978-3-662-25209-3_20openalex-snapshot
Parallel complexity in the design and analysis of concurrent systems
inferred← citeshttps://doi.org/10.1007/978-3-662-48057-1_11openalex-snapshot
A Circuit Complexity Approach to Transductions
inferred← citeshttps://doi.org/10.1007/978-3-662-53015-3_19openalex-snapshot
Fine-Grained Cryptography
showing the first 200 of 856 · page through all 856
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.