STEM Synapse

Subjects

Math & Computer Science Foundations

Today

  1. Paper of the DayPreprint, not yet peer reviewed

    Minimum cores in lattice graphs: zonotope structure and quartic growth

    Picture an endless grid where each point is linked to every point within a set distance.

    Why it matters On grids, groups where every member has most of its links inside the group must be large, growing with the fourth power of link range.

    A core is a group of points in which every member has at least as many links inside the group as outside it, and the question is how small such a group can be. The author shows that every core's outline must include a particular many-sided shape fixed by the grid, and that on a flat grid the smallest core grows with the fourth power of the linking distance. When each point is linked only to its eight surrounding points, the smallest core has exactly 12 points. Finding cores in general networks is also shown to be computationally hard, settling an earlier conjecture.

    Mehrdad, arXiv cs.AI, 17 November 2026.

    Read the paper: Minimum cores in lattice graphs: zonotope structure and quartic growth

Tuesday 17 November

  1. Paper of the DayPreprint, not yet peer reviewed

    Positive Dual Certificates for Real Separated Subset Sums: Chamber Optimality of the Conway-Guy and Bohman Sets, and Exact Values up to Eight

    Pick some positive numbers so that all the sums you can make from them differ by at least 1: how small can the largest number be?

    Why it matters For sets of up to eight numbers whose sums all differ, allowing fractions does not let the largest number drop below the best whole-number answer.

    This is a version, allowing any real numbers, of a famous Erdős puzzle about whole numbers, and a construction by Conway and Guy is a well-known candidate answer. The author splits the problem into regions where it becomes a straightforward optimization and proves that the Conway-Guy set is the unique best choice within its region for every size. A computer search with exact checks then shows that for up to eight numbers, real numbers do no better than whole numbers; with eight, the largest must be 84.

    Notik, arXiv math.CO, 16 November 2026.

    Read the paper: Positive Dual Certificates for Real Separated Subset Sums: Chamber Optimality of the Conway-Guy and Bohman Sets, and Exact Values up to Eight

Monday 16 November

  1. Paper of the DayPreprint, not yet peer reviewed

    Combinatorial Bernoulli Factories with Polynomially Many Coins

    Suppose you have coins whose odds are unknown and want to use them to make a random choice among complicated options, such as ways of pairing people up, that reflects those odds exactly.

    Why it matters Coins with unknown odds can drive a random choice among arrangements, such as pairings, that matches those odds exactly, now with far fewer flips.

    A procedure that does this is called a Bernoulli factory. An earlier one could need an astronomical number of coin flips. The authors give one algorithm, covering every problem where such a procedure can exist, whose expected number of flips grows at a manageable rate with the size of the problem and with how lopsided the coins are. For pairings of n items it needs roughly n to the eighth power flips, where the earlier method needed at least n to the power 2n minus 1.

    Leme et al., arXiv cs.LG, 12 November 2026.

    Read the paper: Combinatorial Bernoulli Factories with Polynomially Many Coins

Sunday 15 November

  1. Paper of the DayPreprint, not yet peer reviewed

    Integer Programming with Polyhedral Constraints on the Image

    Integer programming is the problem of finding the best whole-number solution under a set of constraints, and it underlies scheduling, packing and many other planning tasks.

    Why it matters A wider family of optimisation problems with whole-number answers can now be solved as fast as the standard kind, which also settles an open question.

    This paper extends it to cases where the combined resources a solution uses must themselves satisfy further constraints. The authors give an algorithm, using random choices, whose running time matches the best known for ordinary integer programming, and improves on an earlier method for a more general setting. It yields exact algorithms for versions of the knapsack problem with extra conditions on what is used. It also resolves an open problem about a classic question: whether copies of given numbers can be added up to reach a target.

    Dhar et al., arXiv cs.DS, 12 November 2026.

    Read the paper: Integer Programming with Polyhedral Constraints on the Image

Saturday 14 November

  1. Paper of the DayPreprint, not yet peer reviewed

    Nonlinear lower-tail large deviations at criticality

    Draw a network by taking a set of points and joining each pair with a link at random.

    Why it matters The chance that a random network contains no triangles at all is now known across every range of density, closing the one gap left in a classic question.

    How likely is it that the result contains no triangle, three points all joined to one another? The answer has long been known when links are rare and when they are common, but not at the awkward middle density where the standard mathematical tools give no sharp answer. This paper develops general methods for such in-between cases and fills the gap. The answer changes character abruptly at one particular density, what physicists call a phase transition. For networks avoiding longer loops with an even number of links, the authors show there is no such jump.

    Kwan et al., arXiv math.PR, 13 November 2026.

    Read the paper: Nonlinear lower-tail large deviations at criticality

Friday 13 November

  1. Paper of the DayPreprint, not yet peer reviewed

    The Tournament Equilibrium Set Is PSPACE-Complete, Even under Hereditary Uniqueness

    Some voting rules pick winners from head-to-head contests: for every pair of candidates, which would a majority prefer?

    Why it matters For a voting rule proposed in 1990, checking whether a given candidate wins is now proven extremely hard to compute, even where finding some winner is quick.

    One such rule, proposed by Schwartz in 1990, judges each candidate by the candidates that beat it, in a definition that refers back to itself. Deciding whether a given candidate is among its winners was known to be hard to compute, but not exactly how hard. This paper settles it: the problem belongs to a class believed to be far beyond efficient computation, and stays that hard even under a condition Schwartz conjectured always holds. Yet in the very cases built to be hard, one winner can be found quickly. Finding some winner is easy; confirming a particular one is not.

    Dickey et al., arXiv cs.CC, 12 November 2026.

    Read the paper: The Tournament Equilibrium Set Is PSPACE-Complete, Even under Hereditary Uniqueness

Thursday 12 November

  1. Paper of the Day

    Reconciling Discrete-Time Mixed Policies and Continuous-Time Relaxed Controls in Reinforcement Learning and Stochastic Control

    Reinforcement learning trains a system by trial and error, and it is usually described in steps: at each tick of a clock the system picks an action, often at random according to a rule called a mixed policy.

    Why it matters Treating step-by-step reinforcement learning and its continuous-time version as one problem is now proven sound in one case, not yet in the others.

    Some researchers have recently recast it in continuous time, where the state changes smoothly and randomly, and have treated the two descriptions as fully equivalent. This paper asks how far that holds. For the case where the controller influences only the predictable trend of the system, and not its random fluctuations, the authors prove that the step-by-step method converges to the continuous one as the time steps shrink. Where control also affects the randomness, they set out the technical obstacles that remain.

    Carmona et al., SIAM Review, 12 November 2026. doi:10.1137/25m1782856

    Read the paper: Reconciling Discrete-Time Mixed Policies and Continuous-Time Relaxed Controls in Reinforcement Learning and Stochastic Control