504 papers
The Cs — Cc category explores the fascinating world of computational and cognitive systems, bridging the gap between how machines learn and how human minds process information. This rapidly evolving field examines everything from artificial intelligence algorithms to the neural mechanisms behind decision-making, offering fresh insights into the future of technology and human interaction. By decoding complex patterns in data and behavior, researchers in this space are redefining what it means to think, both biologically and digitally.
At Gist.Science, we ensure these breakthroughs remain accessible to everyone. We process every new preprint from arXiv in this category, transforming dense academic findings into clear, plain-language summaries alongside detailed technical breakdowns. This dual approach allows both curious readers and specialists to grasp the core ideas without getting lost in jargon. Below are the latest papers in this field, offering a direct look at the cutting edge of computational science.
This paper establishes the "Physical Counting Impossibility Theorem," which argues that no fixed-budget physical substrate can provide universal exact proof because the thermodynamic cost of retaining the necessary irreversible records eventually exceeds the system's finite capacity.
This paper investigates the conditions under which a sound arithmetic theory efficiently simulates its extension by establishing unconditional constraints on such simulations and proposing a central conjecture that links the failure of elementary arithmetic to prove consistency implications with the intractability of proving bounded consistency statements.
This paper establishes that preparing near-optimal ground states for random quantum -spin glasses requires circuits with depth growing logarithmically with system size or exceeding any fixed depth, thereby demonstrating that shallow circuits cannot generate the necessary entanglement to close the energy gap between product states and the optimum.
The paper proposes an algorithm claiming to solve the NP-complete 2-MAXSAT problem in polynomial time by transforming it into a DNF maximization problem represented via p*-graphs and a trie-like structure, thereby asserting a proof that P = NP.
This paper resolves an open challenge regarding the \textsc{Monotone 3-Sat-} problem by proving that instances with are always satisfiable, thereby completing a dichotomy theorem that establishes triviality for and NP-completeness for through the introduction of "color structures" and an efficient constructive algorithm.
This paper closes a long-standing gap in the deterministic query complexity of derivative-free convex optimization by establishing a near-quadratic lower bound of for exact function values, thereby matching the best known upper bound up to polylogarithmic factors and extending the result to mixed-integer settings.
This paper reformulates Ilango's effectively zero-knowledge proofs in logical terms to provide simplified proofs of their existence and key properties, and further demonstrates how they can be transformed into genuinely zero-knowledge proofs under a hardness conjecture regarding proof complexity generators.
This paper introduces a framework that disentangles geometric transport from quantum interference in constrained optimization, demonstrating that while constraint-preserving mixing operators alone lack target-seeking ability, engineering coherent phases allows logarithmic circuit depth to achieve certified success probabilities independent of problem size.
This paper proposes a unifying communication complexity model involving two cooperating parties, Alice and Bob, to characterize the regularity of functions with arbitrary output domains and infinite alphabets, generalizing existing results and conjecturing broader applicability.
This paper establishes that, under the Randomised Exponential-Time Hypothesis, learning monotone formulas and approximating the size of monotone circuits are computationally hard problems requiring super-polynomial time, a result achieved by applying novel lifting arguments from proof and communication complexity to extend the hardness of automating Resolution proofs.