Papers for

circuit designers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Proof framework links counting to circuit and space complexity classes

Applicative theories can count

Abstract: Applicative theories offer a proof-theoretic framework for studying complexity. In this paper, we introduce a family of applicative theories to characterize classes ranging from constant-depth circuits to polynomial space. Our approach relies on a simple axiom scheme, the small variations of which allows to capture various forms of counting and alternation. This leads to highly uniform results. When applied on notation, the scheme captures bit counting, yielding a characterization of the functions computable by constant-depth, polynomial-size threshold circuits ($\textbf{FTC}^0$); when applied lexicographically, it allows for the counting of accepting computations, yielding a characterization of the functions in the counting hierarchy ($\textbf{FCH}$). Increasing the logical complexity of the induction formulas allowed in the scheme, we obtain characterizations of the functions computable by bounded Boolean circuits of logarithmic-depth and polynomial-size ($\textbf{FNC}^1$) and of the functions computable in polynomial space ($\textbf{FPSPACE}$). The latter characterization solves an open problem in the field. Finally, we investigate separation results. While it is unknown whether $\textbf{FNC}^1$ and $\textbf{FCH}$ are different, there is an oracle relative to which (relativized) $\textbf{FNC}^1$ is strictly contained in (relativized) $\textbf{FCH}$. We use this fact to separate the theories characterizing them, by exploring their ability to represent higher-order functionals.

Sat 7 NovLogic in Computer Science
The gist
This paper studies how to describe different types of computer calculations using a logical framework called applicative theories. The authors create a family of such theories that can capture computations from very simple circuits to those that need a lot of memory (polynomial space). By changing a simple rule in the theories, they can describe how different kinds of counting happen in computations. This helps to better understand and separate certain complexity classes—groups that classify problems based on how hard they are to compute. They also solve an open problem by characterizing polynomial space computations within this framework.
Open → 2611.10711v1

Polynomial bound found for cycle packing in Eulerian directed graphs

A Polynomial Erdős-Pósa bound for Eulerian digraphs

Abstract: In [Combinatorica 1996], Reed, Robertson, Seymour and Thomas proved Younger's conjecture dating back to 1973 that states that directed cycles have the Erdős-Pósa property. Specifically, they showed that every directed graph $D$ contains either $k$ arc-disjoint cycles or a set of at most $f(k)$ arcs that intersect every directed cycle. The function $f$, depending only on $k$, is however notoriously large--in fact, not even elementary. The first improvement on this function was only very recently provided by Hatzel, Kreutzer, Milani, and Muzi [FOCS 2024] who showed that $f$ can be taken to be an exponential tower of height $8$. In this work, we improve this function to $O(k^4)$ in the case where the digraph is Eulerian. This also answers an open question by Wahlström [Springer Monographs in Mathematics 2018] who asked explicitly when Eulerian digraphs have a polynomial Erdős-Pósa property. The only other known result about Erdős-Pósa on Eulerian digraphs is a result from Seymour [Combinatorica 1996] who showed that $f(k)=k$ when the Eulerian digraph admits a linkless embedding in 3-space, and such an equality is not possible for general Eulerian digraphs. We also complement our positive result, by showing that the result of Seymour cannot be extended to give a linear bound ($O(k)$) on general Eulerian digraphs, by showing that even on Eulerian digraphs the lower bound for the Erdős-Pósa property is $Ω(k \log k)$.

Wed 4 NovDiscrete MathematicsData Structures and Algorithms
The gist
The paper tackles a problem about cycles in special kinds of directed graphs called Eulerian digraphs. It improves how well we can find either many separate cycles or a small set of links that block all cycles. Previous work provided huge bounds that were hard to work with, but the authors show a much smaller, polynomial (fourth power) bound for this problem on Eulerian digraphs. They also show that the simplest kind of bound is not possible for all such graphs, providing a new limitation. This answers an open question about when polynomial bounds can exist in this area.
Open → 2611.06250v1

Neural network model speeds ferroelectric transistor circuit simulations

NN-Based FeFET Compact Modeling for SPICE Simulation

Abstract: Prototyping and early-stage circuit evaluation for emerging transistor technologies require fast and accurate compact models for SPICE simulations. Standard physics-based compact models, such as BSIM, offer high fidelity but demand extensive domain expertise and time-consuming equation formulation for every new physical effect, significantly slowing technology development. Neural network (NN)-based models offer a scalable alternative approach, but they rely heavily on smooth numerical solver data with explicit high-order derivative information. However, measurement data suffers from complex noise patterns, making derivative extraction challenging and complicating NN-based transistor modeling. This work presents a derivative-free NN training framework employing spectral normalization to naturally smooth derivative behavior and filter measurement noise. Using drain current measurements from a fabricated 28 nm ferroelectric device, we design an NN-based compact model that captures the full spectrum of polarization amplitudes and supports dynamic polarization switching in transient simulations. To demonstrate its capability, we deploy the model in a commercial SPICE software to simulate write and read operations for large-scale memory arrays with up to 512x512 size, including parasitic effects. Our approach bridges raw measurements with NN-based SPICE-compatible transistor modeling, significantly reducing model development time and enabling rapid circuit-level prototyping for emerging devices.

Wed 4 NovEmerging Technologies
The gist
Ferroelectric transistors are new devices that need fast and accurate models for testing electronic circuits. Traditional models require complex physics and take a long time to build. The authors use neural networks to create a model that learns from actual measurements, even when the data is noisy. Their model works well in common circuit simulators to predict how memory devices behave in large arrays. This method can make it quicker and easier to design circuits using emerging transistor technologies.
Open → 2611.06127v1

Regular languages fall into three circuit complexity categories

A Circuit Complexity Trichotomy For Regular Languages

Abstract: We establish a trichotomy for the non-uniform, unbounded-fan-in circuit complexity of regular languages: the complexity of every regular language lies in exactly one of $O(1)$, $Ω(\log n)\cap O(\log n\log\log n)$, or $Ω(n)\cap O(n)$. Our main technical contribution is a characterization of the sublinear class in terms of algebra, word congruences, regular expressions, and logic. This class consists precisely of the regular languages computable by constant-depth circuits of size $O(\log^2 n)$, or, equivalently, by circuits of size $O(\log n\log\log n)$ and depth $O((\log\log n)^2)$. Consequently, every regular language of sublinear circuit complexity is definable in $\mathrm{FO}^2[Σ,<,\mathrm{mod}]$, which is contained in wire-linear $\mathbf{AC}^0$. For each of the three classes, deciding membership is $\mathbf{PSPACE}$-complete when the language is specified by a nondeterministic finite automaton. We also obtain a corresponding classification for regular languages with a neutral letter.

Mon 2 NovComputational ComplexityFormal Languages and Automata Theory
The gist
The authors studied how complicated it is to build circuits that recognize regular languages, which are simple patterns processed by computers. They found every regular language fits into one of three clear groups based on how big or complex the circuit needs to be. They also figured out how to tell which group a language belongs to, even if it’s described by a machine called a nondeterministic finite automaton. This helps us understand the fundamental limits of computing simple patterns efficiently.
Open → 2611.03615v1

Algorithm counts feedback vertex sets of all sizes faster than before

Counting Feedback Vertex Sets of All Sizes in Subexponential Time, Conditionally

Abstract: Assuming a Boolean tensor contraction hypothesis (Theorem D.1 of OpenAI's recent preprint refuting the Exponential Time Hypothesis), we study exact feedback vertex set counting in general graphs. For an $n$-vertex, $m$-edge simple graph, we compute the complete size distribution deterministically in $\mathrm{poly}(n+m)\,2^{O(n(\log\log n)^2/\sqrt{\log n})}$ time and polynomial working space. The algorithm combines a whole-edge forest identity, subset-index scalar networks, sparse parity filtering, and disjoint high-degree branching. A binomial inversion recovers the multiplicities introduced by exceptional-set guesses. The counting interface supports fixed vertices, minimum solutions, and unranking. Component markers yield induced-tree and induced-path counts within the same bound. Sparse Hamilton, forest, and Steiner edge-tree counting follow from the scalar encoding.

Mon 2 NovData Structures and Algorithms
The gist
A tough problem in graph theory is to count specific sets of points called feedback vertex sets, which help understand cycles in networks. The authors present a new method that counts how many of these sets there are for every possible size, doing so more efficiently than traditional approaches—though their speed depends on a certain computational hypothesis. Their approach also extends to counting other related structures like trees and paths within graphs. This could help in areas where understanding complex networks and their cycle structures is important.
Open → 2611.02548v1

Continuous kinetic model improves circuit simulation of molecular memristors

Continuous Kinetic Model of Counterion-Mediated Redox Switching in 14-Bit Molecular Memristors for Analog In-Memory Computing

Abstract: Kinetic molecular memristors offer a compelling path toward high-density analog in-memory computing by achieving 14-bit precision, wherein discrete redox transitions and counterion displacements dictate non-volatile conductance across a deterministic energy landscape. However, integrating these nanoscale kinetics into macroscale circuit simulators has remained bottlenecked by derivative discontinuities and solver convergence failures. Here, we present a physics-inspired continuous kinetic model that bridges microscopic molecular transport with scalable circuit architectures. By casting discrete intramolecular states, counterion relaxation dynamics, and Marcus-Hush-Chidsey electron transfer rates into continuously differentiable state variables, we derive a robust, Spectre-compatible compact model and a matching vectorized Python solver. This work culminates in a unified computational platform to reliably predict the behavior of complex circuits built on these molecular memristors.

Mon 2 NovHardware Architecture
The gist
Molecular memristors are tiny devices that switch electrical signals with very high precision, useful for storing data inside computer chips. The authors found a way to describe how these devices work smoothly, avoiding jolts or breaks that made simulating whole circuits difficult before. Their new model simplifies the complex chemistry and movement of charged particles into a form that existing simulation tools can use reliably. This advance helps engineers predict how circuits with molecular memristors behave, enabling better designs for future computing hardware.
Open → 2611.02520v1

Exponential complexity lower bounds for cubic polynomial products over prime fields

Exponential Lower Bounds for Products of Cubic Polynomials over Prime Fields

Abstract: We study exact representations of explicit signed modular predicates on $\{-1,1\}^n$ as products of bounded-degree polynomials over prime fields, measured by total variable-occurrence cost. Our main result is an exponential lower bound for products of cubic polynomials. Over $\mathbb F_3$ the proof is self-contained: every cubic factor in a nonvanishing product is a unit on the sign cube, the unit identity forces bounded affine-observation complexity, and a simultaneous clustering argument converts this structural compression into an exponential occurrence lower bound. We also give an alternative reconstruction route that isolates the quadratic structure behind the cubic classification. We then extend the cubic theorem to every fixed prime field $\mathbb F_p$ of characteristic greater than three for odd target modulus $q$ coprime to $p$. The only non-elementary structural input in this extension is Karam's restricted-range rank theorem; the conversion from multiplication to parity and the $p$-tuple clustering argument are proved explicitly. Finally, we establish a coefficient-field-independent degree-lifting principle. If a lower bound is known at one fixed degree, restriction to a large independent set yields a quantitative lower bound at the next degree. In particular, the exponential cubic theorem implies $ L^{(p,q)}_4(n)=Ω_{p,q}\!\left(\frac{n^4}{(\log(2+n))^3}\right). $ For the characteristic-three core this already gives a lower bound for a restricted mixed-modulus circuit class.

Mon 2 NovComputational Complexity
The gist
This paper shows that certain mathematical functions cannot be represented efficiently by multiplying simple cubic polynomials taken from prime number-based number systems. The authors prove that to exactly describe these functions, you need an exponentially large number of occurrences of variables in such polynomial products. Their results hold for fields related to prime numbers, including specific cases like three-element fields, and extend to more general prime fields. They also provide a method to extend these lower bounds to polynomials of higher degree. This helps explain the limitations of certain algebraic circuit designs.
Open → 2611.02385v1

New complexity results clarify choosing parity subsets in cryptography

The Complexity of Choosing Parity Projections

Abstract: Cube attacks in cryptanalysis seek small sets of Boolean variables (cubes) whose parity sum is constant. We study the bounded constant derivative problem introduced by Smirnov (2026), which seeks a smallest cube with sum 1, and its sum-0 analogue. Despite their similarity, the problems differ sharply in parameterized complexity: the sum-1 problem admits a $2^{O(k^2)}\operatorname{poly}(N)$-time algorithm, where $k$ is cube size, whereas the sum-0 problem is not fixed-parameter tractable unless $\mathrm{FPT}=\mathrm{W}[1]$. Without a bound on cube size, both problems are $Σ_2^{\oplus\mathrm{P}}$-complete and NP-hard to approximate within $N^{1-\varepsilon}$ for every fixed $0<\varepsilon<1$. Our hardness proofs use a crown construction that embeds maximal monomials of parity-projected circuits into positive 2CNF. This yields completeness and inapproximability results, as well as a dichotomy for Boolean constraint languages of arity at most two: the bounded constant derivative problem is in P when all relations are affine and $Σ_2^{\oplus\mathrm{P}}$-complete otherwise. We also give algorithms parameterized by the number of quadratic rounds, treewidth, or ordered branching-program width, with lower bounds for the first two unless $\mathrm{NP}\subseteq\mathrm{SUBEXP}$. The treewidth lower bound holds for circuits; the case of 2CNF remains open.

Fri 30 OctComputational Complexity
The gist
This paper explores the difficulty of finding special groups of true/false variables called cubes in cryptanalysis, which help analyze the security of encryption methods. The authors show that two similar problems about these cubes differ greatly in how quickly they can be solved, depending on subtle details. They establish that without size limits, these problems are very hard computationally and difficult to approximate closely. The researchers provide exact classifications of these problems' difficulty and offer some algorithms for specific structured cases, along with evidence that improving these algorithms is unlikely.
Open → 2611.00289v1

Ai models improve analog layout programs by reusing code structures

The Code Behind the Layout: AI Agents for Analog Layout Generators

Abstract: Analog layout remains largely manual and hard to automate. Generator frameworks such as gLayout express layouts as programs, producing layouts from parameterized, design-rule-aware generators; however, writing such generators still takes expert effort. Large language models (LLMs) could now write generator code, and frontier models can even draw layout geometry from design intent. This raises a practical question: if a model can draw the layout itself, what does a generator framework still contribute, and is applying these models to a generator framework better than having them draw a layout from scratch? Through controlled experiments on gLayout in SKY130, we find that the main obstacle to drawing a layout directly is its time and token cost, and that the main advantage of a model building on a generator framework is reusability. Its verified primitives keep each model edit small enough to check, and its parameters allow a single edit to be evaluated across an entire family of layouts. Accordingly, a model is most effective when it develops the layout from the generator source of the family that the design intent belongs to, and tests each edit on the family members most likely to fail, so that one verified change improves every layout the generator produces. The results of these family tests can then serve as supervision for a local model, which learns edits that hold across the family at a fraction of the inference cost.

Wed 28 OctHardware ArchitectureArtificial Intelligence
The gist
Designing circuits by hand is hard and slow, especially for analog layouts. The paper shows that while AI models can draw circuit layouts from scratch, it’s much more efficient to have them work with existing layout programs. These programs use reusable building blocks, letting AI make small changes that improve many designs at once. The authors find this method saves time and makes it easier to check if the changes work across similar circuit families.
Open → 2610.38426v1

Linear time test finds bend free drawings for special planar graphs

Linear-Time FPT Rectilinear Planarity Testing of Series-Parallel Graphs

Abstract: A planar graph is rectilinear planar if it admits a planar orthogonal drawing without bends. For series-parallel graphs in the variable embedding setting the best known testing algorithm takes $O(n^2)$ time. We show that rectilinear planarity of a series-parallel graph with maximum degree four can be tested in $2^{O(k)}\cdot n$ time, where $k$ is the number of degree-4 vertices; the planar embedding is not fixed. In particular, the running time is subquadratic when $k=o(\log n)$. Each node of the SPQ$^*$-tree stores the set of its admissible spiralities; we show that this set is a union of $2^{O(k)}$ arithmetic progressions of step two. All proofs are in the paper and are additionally verified in Lean 4 with Mathlib.

Tue 27 OctData Structures and Algorithms
The gist
Some graphs can be drawn on paper with only straight horizontal and vertical lines and no bends, which can be useful for clear diagrams. Testing if such a drawing exists usually takes a long time for certain graphs. The authors show a way to do this test much faster for a special kind of graph called series-parallel graphs with a limited number of points having four connections. They use a clever mathematical structure and prove their results with computer verification. This means certain clean drawings can now be checked more quickly.
Open → 2610.37018v1

New circuit size limits strengthen understanding of Boolean function complexity

Short Point Lists for CNFs and Stronger Constant-Depth Circuit Hardness

Abstract: We give a short-description decomposition of bounded-width CNFs. For every fixed $\varepsilon>0$, every width-$b$ CNF on $m$ variables is an exact disjoint union of at most $2^{\varepsilon m}$ width-$b$ CNFs, each determined by $2^{O_\varepsilon(b)}\log(m+1)$ satisfying assignments. For every fixed $d\ge3$, we prove a worst-case size lower bound of $2^{Ω_d((n\log n)^{1/(d-1)})}$ against depth-at-most-$d$ unbounded-fan-in AND/OR circuits with input negations for three polynomial-time Boolean families: inverse trace over binary fields, the Goldreich--Tal trilinear function, and OpenAI's polynomial evaluator with its original parameters. All parameter bits count as inputs. For inverse trace, every such circuit of size at most $S$, where $n\le S\le2^{c_dn^{1/(d-1)}}$, has uniform sign correlation at most $2^{-η_dn\log\log S/(\log S)^{d-1}}$. Here $c_d,η_d>0$ depend only on $d$. This improves on the classical parity correlation bound. The lower bounds combine the decomposition with restriction arguments; the correlation bound additionally uses common partial decision trees. We also construct exact nonuniform AND/OR circuits for inverse trace of size $2^{O(n^{2/3})}$ at depth eight and $2^{O(\sqrt n\log n)}$ at depth nine. For every fixed integer $h\ge2$, the construction gives depth-$(4h+1)$ circuits of size $2^{O_h(n^{1/h}\log n)}$. The upper bounds implement finite-field evaluation and interpolation using circuits that enumerate intermediate states.

Mon 19 OctComputational Complexity
The gist
This paper studies how certain Boolean functions, which involve true and false values, can be described or computed by special types of logical circuits. The authors found a way to break down complex formulas into simpler parts and proved that even the best possible small logical circuits cannot compute these functions efficiently when the circuits have limited depth. They also built some circuits that compute these functions but showed these circuits have to be quite large. These results help us understand the limitations of certain types of computation.
Open → 2610.27127v1

Optimal single-track gray codes found for all prime lengths up to 47

Optimal single-track Gray codes from Gray-ordered necklaces

Abstract: A single-track Gray code of length $n$ is a cyclic Gray code of $n$-bit words in which every column is a cyclic shift of the first. For prime $n$ the longest possible period is $2^n-2$. Whether it is attained for every prime has been open since Hiltgen, Paterson and Brandestini introduced these codes in 1996, and optimal codes were known for primes $n\le 19$. We show that a conjecture of Degni and Drisko (2007) on the reflected Gray code order of necklaces implies optimal single-track Gray codes for every prime. Their list of necklaces, conjecturally a Gray path for prime $n$, closes into a Hamilton cycle of the necklace graph after $(n-3)/2$ explicit Pósa rotations, and such a cycle lifts to an optimal code. This implication is formalized in Lean 4. Together with computation it gives optimal single-track Gray codes for every odd prime $n\le 47$: for $n\le 37$ explicit codes checked word by word by a program independent of the generator, and for $n=41$, $43$ and $47$ codes obtained from the implication after the Degni-Drisko property was verified at these lengths by two independently written programs.

Sat 17 OctDiscrete MathematicsInformation Theory
The gist
This work solves a long-standing open problem about special sequences called single-track Gray codes, which list binary strings so that each changes just a bit at a time in a repeating pattern. The authors link a previous mathematical conjecture about ordering sets called necklaces to the existence of longest possible such sequences for every prime number length. They verify this via computer checks up to length 47, giving optimal codes for all odd primes up to that point. This combines theoretical insight with computation to advance understanding of these code patterns.
Open → 2610.24758v1

Low-latency adders designed using printed memristors speed up computing

Cross-Layer Co-Design of Low-Latency Stateful Logic Adders with Printed Memristors

Abstract: Data movement between memory and processing units remains a major bottleneck in data-centric systems. Memristive Stateful Logic (SL) addresses this problem by performing Boolean operations directly on stored resistive states. However, arithmetic efficiency depends jointly on the device-supported logic primitive set, the dependency structure of the resulting operation sequence, and its mapping to datapath architectures. While prior designs typically optimize device, logic, and architecture layers separately, we jointly consider them to co-design a stateful adder. We experimentally demonstrate a mixed MAGIC and FELIX logic primitive set on printed Electrochemical Metallization (ECM) memristors and derive a full adder sequence optimized for inter-bit carry propagation. Mapping this sequence to bit-serial, bit-parallel, and bit-pipelined datapaths reduces the latter two to 2n+6 cycles for an n-bit addition. For 32-bit addition, this requires 60-88% fewer cycles than prior SL adders. Across four representative workloads, we achieve 3.7x-16.4x speedup over prior. These results show how cross-layer co-design can translate into improved workload-level performance.

Wed 14 OctEmerging Technologies
The gist
Moving data between memory and processors slows down computers. The authors worked on a way to do math directly where data is stored using special devices called memristors. They created a method combining different logic steps and hardware designs to make adding numbers faster. Their design uses fewer steps than older methods, making addition tasks run much quicker. This shows that designing devices and computing methods together can lead to better performance.
Open → 2610.20109v1

Boundaries of majority function approximation using torus polynomials

Majority and Torus Polynomials: Bounded-Lift Lower Bounds and Explicit Constructions

Abstract: Bhrushundi et al. (2019) introduced torus polynomial approximation as an approach to separating Majority from $ACC^0$. In this model, approximation is measured modulo integers. Krishan and Vishwanathan (2026) developed a duality framework for lower bounds and posed five open problems. We resolve two of these, concerning integer lifts and explicit polynomial approximations. An integer lift records the integer shifts that turn a torus approximation into an ordinary real approximation. We show that a degree-d torus polynomial approximating Majority with error at most 1/8 and lift contained in an interval of width $B$ must satisfy $d(B + 1) = Ω(n)$. This rules out low-degree approximating polynomials with lifts in {-1, 0, 1}, answering their Open Problem 2. We also answer Open Problem 5 by giving, for every Boolean function on $n \geq 1$ variables, an explicit torus polynomial approximation of degree at most $n - 1$. Its error is optimal: zero when the accepting set has even cardinality and $2^{-n-1}$ otherwise. The results presented were discovered and formalized in Lean using GPT-6 Astra.

Tue 13 OctComputational Complexity
The gist
This paper explores limits on how well certain polynomials called torus polynomials can approximate the majority function, which decides if most inputs are ones or zeros. The authors show that if these polynomials use only small integer shifts, they must have high complexity. They also build explicit polynomials that approximate any Boolean function exactly or with very small error. These findings help understand fundamental challenges in computational complexity and could guide future design of algorithms.
Open → 2610.19174v1

Almost all Boolean functions need midpoint degree polynomials

Almost every Boolean function has central threshold degree

Abstract: The polynomial threshold degree (or threshold degree) of a Boolean function is the least degree of a real polynomial whose sign represents it. We prove that almost every Boolean function has polynomial threshold degree among the central one or two integers. More precisely, a uniformly chosen Boolean function on $n$ variables has threshold degree $\lfloor n/2\rfloor$ or $\lceil n/2\rceil$ except with probability at most $\exp(-c2^{n/2}/n)$, for an absolute constant $c>0$ and all sufficiently large $n$. A parity example gives a lower bound on the exceptional probability whose exponent differs from ours by a factor of order $n$. The proof relates polynomial sign representation to recovery of Reed--Muller codes from random erasures, and combines sharp-threshold estimates with bounds on generalized Hamming weights and minimum distance.

Sat 10 OctDiscrete MathematicsInformation Theory
The gist
The authors studied how complex it is to represent Boolean functions using polynomials that output positive or negative signs matching the function. They found that for most Boolean functions with many variables, the minimum polynomial degree needed is almost exactly half the number of variables. This result sharpens understanding of how complex Boolean functions can be from a polynomial perspective. The proof connects this problem to ideas in error-correcting codes and probabilistic thresholds.
Open → 2610.15057v1

Randomized affine filters link satisfiability to complexity class collapse

Near-Inverse-Linear Barriers for Explicit Affine Witness Isolation

Abstract: We study randomized nonuniform polynomial-size transformations that output explicit binary affine filters for circuit inputs whose nonempty satisfying sets are affine. The filter may depend on the entire input description; no affine basis is supplied. For every fixed $δ<1$, a worst-case singleton success guarantee $Ω(n^{-δ})$, where $n$ is the witness arity, implies $NP\subseteq P/poly$. More generally, any success guarantee $ω(\log n/n)$ yields satisfiability circuits of size $(s+2)^{O(1)}2^{o(v)}$ for length-$s$ descriptions with at most $v$ witness variables, hence subexponential in $v$ when $s=v^{O(1)}$. Conversely, SAT search-to-decision gives deterministic perfect isolation, making polynomial-resource fixed-exponent strong affine isolation equivalent to $NP\subseteq P/poly$. For explicit unions of at most $n^β$ affine components, success $Ω(n^{-δ})$ implies the same collapse whenever $β,δ\ge0$ and $β+δ<1$. The inverse-linear endpoint is not claimed.

Thu 8 OctComputational Complexity
The gist
The paper explores special filters that can recognize certain structured solutions in logical problems. These filters work when the solutions form neat, affine shapes, but creating them reliably would imply a major breakthrough in computer science theory. Specifically, if such filters succeed often enough, it means a hard complexity problem (NP) could be solved easily with small advice information, collapsing important complexity classes. The authors establish tight connections between how well these filters perform and fundamental limits in computational complexity.
Open → 2610.11432v1

Matroid colorings can differ for lists versus simple sets

A note on the list chromatic number of two matroids

Abstract: We study list coloring of common independent sets of two matroids. We construct a graphic matroid $M_1$ and a partition matroid $M_2$ with common chromatic number two and common list chromatic number three, showing that the two parameters need not be equal. This resolves a question raised by Király, later stated as a conjecture by Aharoni, Berger, Guo, and Kotlar. We also show that if two strongly base-orderable matroids are each $2$-colorable, then their intersection is $2$-list-colorable.

Mon 5 OctDiscrete Mathematics
The gist
When trying to color objects so that certain groupings don’t share colors, two special combinatorial structures called matroids are studied. The authors show that the minimum number of colors needed when each element has its own color list can be larger than when colors are chosen freely. They give an example where two matroids require only two colors generally but need three when restricted to lists, solving a previously open question. They also prove that under certain conditions, two matroids each colorable with two colors are still colorable with two colors even when lists are assigned.
Open → 2610.07318v1

Hitting sets simplify testing specific structured polynomials efficiently

Hitting Sets for Polynomials with Small Partial Derivative Spaces

Abstract: We give an explicit hitting set of size $\text{poly}(n,d,r)$ for the class of $n$-variate degree-$d$ polynomials whose partial derivative space is bounded by $r$, over any field $\mathbb{F}$ of characteristic zero. In particular, this yields a polynomial sized hitting set for the class of depth-$3$ powering circuits. The main technical insight is the construction of a "formal derivation'' and properties of the associated Wronskian with respect to this derivation, which was previously studied by Moura [Moura_2004] in a very different context. The proofs in this paper are elementary and completely self-contained. AI disclosure: The proof of this result was obtained during conversations [astra_proof] with OpenAI GPT-6 Astra. The proof presented in this writeup is a rewriting (in the authors' words) of the proof obtained by the AI model in a form that we believe is understandable to researchers.

Mon 28 SeptComputational Complexity
The gist
The paper finds a way to efficiently test if certain complex math expressions, called polynomials, are zero without having to check every possible input. These polynomials have a special property that limits their complexity, defined by something called the partial derivative space. The authors create explicit sets of test inputs that are much smaller but still effective. This helps with understanding and working with certain circuit models in computer science. They also use an old mathematical tool called a Wronskian in a new way to make their proof simple and clear.
Open → 2609.34436v1

Circuit size limits for computing majority clarified after decades

Optimal Shallow Circuits for Majority

Abstract: Four decades on, Håstad's classical $2^{Ω(n^{1/(d-1)})}$ lower bound for depth-$d$ circuits computing Parity remains the best known $\mathrm{AC}^0$ circuit lower bound for any explicit function. Majority has long been a compelling candidate for stronger lower bounds: the most natural circuits computing it are substantially larger than those for Parity and have repeatedly been conjectured to be optimal. We present a simple construction, found by GPT-6 Astra, of depth-$d$ circuits of size $2^{O(n^{1/(d-1)})}$ for any symmetric function. This result settles the asymptotic $\mathrm{AC}^0$ circuit complexity of Majority, matching Håstad's lower bound.

Sun 27 SeptComputational Complexity
The gist
People have tried for decades to understand how complex computer circuits need to be to decide if more than half of a list of bits are ones, which is called the Majority function. Earlier, the best known lower limits for circuit complexity were for a simpler function called Parity. The paper presents a new way to build circuits for Majority with sizes matching those theoretical limits exactly. This settles a long-standing question about how efficiently Majority can be computed with shallow circuits.
Open → 2609.34029v1

Biplanar graphs with small independence number need at most nine colors

Biplanar graphs with independence number two are 9-colorable

Abstract: A graph is biplanar if it is the union of two planar graphs on the same vertex set. The largest chromatic number of a biplanar graph is known to lie between 9 and 12. The lower bound comes from Sulanke's graph, which has independence number 2, and a biplanar graph on 19 vertices with independence number 2 would have chromatic number at least 10. Gethner and Sulanke asked in 2009 whether such a graph exists. We show that it does not, and more generally that every biplanar graph with independence number at most 2 is 9-colorable. The proof embeds a hypothetical counterexample in the union of two sphere triangulations, enumerates with SAT modulo symmetries the 3271 graphs that pass a necessary filter for the complement of such a union, and shows with a SAT solver that none of them is such a complement; a matching argument reduces the general statement to this computation and one further case on 18 vertices. The computational part of the proof, including the completeness of the enumeration and every refutation, is checked in Lean 4, assuming three classical facts about planar graphs. The Lean development, the SAT instances, and the enumeration certificates are available on Zenodo.

Wed 23 SeptLogic in Computer Science
The gist
This paper studies a type of graph made by combining two graphs that can be drawn without crossing lines. When coloring such graphs—assigning colors so that connected points differ—the question is how many colors are needed if no three points are all separate from each other (independence number 2). The authors prove that these graphs can always be colored with at most nine colors, resolving an open question. They reached this conclusion by combining mathematical reasoning with computer checks verified by formal proof software.
Open → 2609.28102v1

Proper vertex coloring through edge weights improved by vertex cover parameter

Vertex-Coloring Edge-Weighting: Kernelization and Generalization

Abstract: An edge weighting of a graph induces a coloring of its vertices in which the color of a vertex is the total weight of the edges incident with it. Such an edge weighting is proper if adjacent vertices always receive distinct colors. Deciding whether a graph admits a proper weighting is known to be NP-complete for the weight set $\{0,1\}$, and also for $\{1,2\}$. In recent work (arXiv:2604.12363) we showed that both problems are FPT parameterized by the vertex cover number $k$, but it was open -- to the best of our knowledge -- whether either parameterized problem had a polynomial kernel. In this work, we show that both problems have polynomial kernels when parameterized by $k$. We also show that both problems are W[1]-hard parameterized by treedepth, answering another question from our earlier work. We then study the pre-weighted versions of the two problems, in which the weights of some edges are fixed in advance, and the task is to extend the assignment to a proper weighting of the whole graph. We show that both pre-weighted problems are FPT parameterized by the vertex cover number $k$. For the $\{1,2\}$ version the running time is $2^{O(k \log k)} \cdot n$; for the $\{0,1\}$ version we obtain the same running time when every pre-weight is $1$, and a slower FPT algorithm in the general case. We also show that both pre-weighted problems are W[1]-hard parameterized by either of (i) the feedback vertex set number or (ii) the treedepth of the input graph. Since a graph with no pre-assigned weights is a special case, our algorithms for the pre-weighted versions solve the two original problems as well, in time $2^{O(k \log k)} \cdot n$, significantly improving on the bound of $2^{O(k^4)} \cdot n^{O(1)}$ from our earlier work.

Wed 23 SeptData Structures and AlgorithmsComputational ComplexityDiscrete Mathematics
The gist
The authors study a way to color the nodes of a graph based on the weights assigned to connecting edges, ensuring neighboring nodes have different totals. They focus on cases where weights come from just two numbers and prove it’s very hard to decide if such a coloring exists in general. However, they show that if the graph has a small vertex cover (a set of nodes touching all edges), they can simplify the problem significantly and solve it efficiently. This work extends to situations where some edges already have fixed weights and explores other graph properties where solving remains difficult.
Open → 2609.27719v1

Relationships among sensitivity measures of symmetric Boolean functions

Sensitivity and Block Sensitivity of Elementary Symmetric Boolean Functions of Arbitrary Degree

Abstract: Let $σ_{n,d}$ denote the elementary symmetric Boolean function of $n$ variables and degree $d$. We completely determine the sensitivity, average sensitivity, and block sensitivity of $σ_{n,d}$ for every $1\le d\le n$. Using Lucas' theorem, we obtain a uniform binary description of the Hamming-weight value sequence, from which the sensitivity and average-sensitivity formulas follow and the computation of block sensitivity reduces to at most four explicit candidates. Combining these results with the arbitrary-degree formula for certificate complexity, we determine the exact relations among sensitivity, block sensitivity, and certificate complexity. We also prove a general result for symmetric Boolean functions: every nonconstant symmetric Boolean function $f$ satisfies \[ \bs(f)\le \max\{s(f),C(f)-1\}. \] Consequently, only the three patterns \[ s=\bs=C,\qquad s=\bs<C,\qquad s<\bs<C \] can occur for nonconstant symmetric Boolean functions. For elementary symmetric Boolean functions, we give necessary and sufficient conditions for each of these three patterns, thereby completely classifying the relations among $s(σ_{n,d})$, $\bs(σ_{n,d})$, and $C(σ_{n,d})$. In particular, we obtain a necessary and sufficient characterization of the full strict hierarchy \[ s(σ_{n,d})<\bs(σ_{n,d})<C(σ_{n,d}), \] and exhibit infinite families for which it holds.

Sun 20 SeptDiscrete Mathematics
The gist
This paper studies how different ways of measuring the complexity of certain logical functions called elementary symmetric Boolean functions relate to each other. The authors find exact formulas for three sensitivity measures—sensitivity, average sensitivity, and block sensitivity—for all degrees of these functions. They also prove general rules that restrict how these measures can be arranged relative to one another. Finally, they completely classify when each pattern of relationships can happen and provide examples where these patterns occur.
Open → 2609.23781v1

Local decision trees link sumset patterns to circuit lower bounds

Sumset Structure in Local Computation

Abstract: We introduce and study a new model of decision trees that lies at the frontier of provable circuit lower bounds. We study $\ell$-local decision trees, in which each internal node queries an $\ell$-local function of the input. We show that sufficiently strong lower bounds for $\ell$-local decision trees would imply several breakthrough circuit lower bounds, including super-linear size lower bounds for log-depth circuits and improved bounds for unrestricted-depth circuits. Previously, such consequences were known to follow from strong lower bounds for depth-$3$ circuits, which has been the main prior approach in attempting to prove these results. Since local decision trees are strictly weaker than depth-$3$ circuits, this provides a formally easier route to the same circuit lower-bound consequences. We prove essentially optimal lower bounds for a weaker variant that we call oblivious $\ell$-local decision trees, where all nodes at the same depth query the same function. Our lower bounds follow from a new technique that uncovers sumset structure in local maps, and our hard functions are sumset dispersers, sumset condensers, and directional affine dispersers. Along the way, we give an explicit construction of a sumset condenser with small entropy loss. As an additional contribution, we initiate the study of degree-$2$ decision trees, in which each query is a quadratic polynomial of the input. We show that proving lower bounds in this model is a natural stepping stone toward constructing dispersers for degree-$2$ variety sources, which imply improved circuit lower bounds for unrestricted depth circuits. We prove nearly maximal lower bounds for the oblivious variant of the model.

Sat 19 SeptComputational Complexity
The gist
Computers run programs made of small steps called circuits, and understanding their limits is a big challenge. This paper studies a new kind of decision tree that asks about small pieces of the input, which can help prove limits on how efficiently these circuits work. The authors show that proving certain bounds for these local decision trees could lead to breakthroughs in understanding circuit complexity. They also find strong limits for simpler versions of these trees by exploring hidden patterns in special sets of sums called sumsets. Additionally, they look at decision trees based on quadratic queries, pointing toward future circuits that are harder to simplify.
Open → 2609.22732v1