Four-dimensional Einstein Dehn filling is impossible.
problem Complex-hyperbolic Einstein Dehn filling in four dimensions.
method Proof of impossibility.
result Complex-hyperbolic Einstein Dehn filling cannot be performed in dimension four.
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,694 papers · 148 categories
Trend · papers per month
48 results for “impossibility proof”
The study of tiling homology on flat surfaces, proving impossibility of certain tilings.
problem Proving the non-existence of polyomino tilings on specific square-tiled surfaces.
method Study of homology groups for topological tilings, using coloring proofs.
result Several results about the non-existence of polyomino tilings on certain square-tiled surfaces.
Large language models can't efficiently reason conditionally in a distribution-free setting.
problem Impossibility of conditional PAC-efficient reasoning in large language models.
method Proof of impossibility in a distribution-free setting for non-atomic input spaces.
result Any algorithm achieving conditional PAC efficiency must defer to the expert model with high probability.
Researchers prove it's impossible to partially recover graph alignments in certain conditions.
problem Recovering vertex correspondence between two random graphs with correlated edges.
method Used the probabilistic method to build automorphisms between tree components of a subcritical Erdös-Rényi graph.
result Proved an impossibility result for partial recovery in the sparse regime with constant average degree and correlation.
Researchers prove inner product recovery is impossible in latent space models.
problem Recovering inner products in latent space models with random geometric graphs.
method Rate-distortion theory applied to Gaussian or spherical latent locations.
result Impossible to recover inner products if dimensionality exceeds , matching positive results' conditions.
This paper shows that one cannot learn the probability of rare events without imposing further structural assumptions. The event of interest is that of obtaining an outcome outside the coverage of an i.i.d. sample from a discrete distribution. The probability of this event is referred to as the "missing mass". The impo…
Paper proves impossible for large language models to control hallucinations without sacrificing other properties.
problem Achieving truthful knowledge representation, semantic information conservation, and knowledge-constrained optimality simultaneously in large language models.
method Modeling inference as an auction of ideas, using mechanism design, proper scoring rules, and transformer architecture analysis.
result No LLM can simultaneously achieve all four essential properties without violating at least one.
No fair and strategy-proof automated market maker exists for more than two assets.
problem Designing a fair and strategy-proof automated market maker for multiple assets.
method Analyzing the weighted-product family of aggregation rules and their properties.
result No aggregation rule is both fair and strategy-proof for more than two assets.
This paper sets thresholds for recovering vertex correspondences in partially correlated graphs.
problem Recovering hidden vertex correspondences in partially correlated graphs.
method Proposed partially correlated Erdős-Rényi graphs model; information-theoretic thresholds; correlated functional digraphs.
result Optimal rates for partial and exact recovery of vertex correspondences.
Theoretical limits on verifying self-improving systems without risking unbounded utility.
problem Formalizing and proving the limits of safety verification for self-improving systems.
method Developed dual conditions and used Holder's inequality, NP counting method, and Lipschitz bounds to establish impossibility and ceiling results.
result A classifier-based safety gate cannot simultaneously permit unbounded beneficial self-modification and bounded cumulative risk.
Empty core found in max-loss non-centroid clustering.
problem Core stability in non-centroid clustering under max-loss objective.
method Proof for all k≥3 and n≥9 agents, computer-aided proof for 2D Euclidean points.
result Core can be empty in non-centroid clustering under max-loss objective.
Machine fairness is impossible to achieve fully due to historical biases.
problem Machine learning models inherit biases from historical data, making it impossible to satisfy fairness metrics simultaneously.
method Presented a causal perspective to the impossibility theorem of fairness.
result It is impossible to satisfy fairness metrics like demographic parity, equal opportunity, and equalized odds simultaneously.
We consider the Degree-Corrected Stochastic Block Model (DC-SBM): a random graph on nodes, having i.i.d. weights (possibly heavy-tailed), partitioned into asymptotically equal-sized clusters. The model parameters are two constants and the finite second moment of the weights $Φ^{…
In this article we prove the impossibility of some disentanglement puzzles, first building mathematical models that reflect the essential characteristics of these puzzles.
There are many theorems in the differential geometry literature of the following sort. Let M be a complete Riemannian manifold with some conditions on various curvatures, diameters, volumes, etc. Then M is homotopy equivalent to a finite CW complex, or M is the interior of a compact, topological manifold with boundary.…
TWM doesn't reduce delta in PDLPs, proving impossibility.
problem TWM in PDLPs doesn't uniformly reduce portfolio delta.
method Proved TWM's condition is self-contradictory and showed impossibility.
result No TWM can uniformly reduce portfolio delta.
An impossibility result shows limitations in learning symmetries and equivariant functions.
problem Learning symmetries and equivariant functions simultaneously is impossible under certain conditions.
method Careful study of approximation for groups and semigroups, analysis of neural networks.
result Linearly equivariant networks can be used to learn equivariant functions, but group-convolutional networks have limitations.
No feature ranking can be faithful, stable, and complete when features are collinear.
problem The impossibility of creating a feature ranking that is simultaneously faithful, stable, and complete when features are collinear.
method Proving the impossibility, quantifying it for four model classes, resolving it via ensemble averaging (DASH), and machine-verifying it with Lean 4 theorems.
result No method lies outside the dichotomy of faithful-complete methods (unstable, with rankings that flip up to 50% of the time) and ensemble methods (stable, reporting ties for symmetric features).
Two impossibility theorems show formal alignment certification is impossible for AI systems.
problem Formal certification of AI alignment over open-ended domains is impossible.
method Two independent impossibility theorems: Semantic and Statistical barriers.
result No procedure can simultaneously satisfy soundness, completeness, and tractability.
Paper proves impossibility of three desirable properties in node embedding.
problem Understanding limitations of node embedding methods.
method Axiomatic approach to node embedding, proving impossibility of three properties.
result No node embedding method can satisfy all three desirable properties simultaneously.
A new method for variable importance measures without impossible data.
problem Using impossible data for variable importance measures in black box models.
method Cohort Shapley, a method grounded in economic game theory using only observed data.
result Cohort Shapley provides a more trustworthy explanation of black box models' decisions.
Hass and Scott's example of a 4-valent graph on the 3-punctured sphere that cannot be realized by geodesics in any metric of negative curvature is generalized to impossible configurations filling surfaces of genus with punctures for any and .
Paper proves MS convergence for radially symmetric kernels with large bandwidths.
problem Proving convergence of mean shift algorithm with radially symmetric kernels.
method Analyzes convergence of mean shift algorithm with radially symmetric, positive definite kernels.
result Guaranteed convergence for sufficiently large bandwidth in any dimension.
Modeling of a wide class of physical phenomena, such as crystal growth and flame propagation, leads to tracking fronts moving with curvature-dependent speed. When the speed is the curvature this leads to one of the classical degenerate nonlinear second order differential equations on Euclidean space. One naturally wond…
Clean intersections of Lagrangian knots in 3D are impossible.
problem Prohibiting clean intersections of certain knots in 3D symplectic geometry.
method Symplectic field theory and algebraic constraints on augmentation varieties.
result No Hamiltonian diffeomorphism can cleanly intersect a specific type of knot's conormal bundle.
The seminal idea of quantum money not forgeable due to laws of Quantum Mechanics proposed by Stephen Wiesner, has laid foundations for the Quantum Information Theory in early '70s. Recently, several other schemes for quantum currencies have been proposed, all however relying on the assumption that the mint does not coo…
New protocol identifies impossible edge orientations in causal graphs.
problem Causal-discovery algorithms cannot distinguish edge directions without assumptions.
method Discrete impossibility certificates and oracle queries.
result Upper bound of expert interactions for DAG recovery.
Study on Yang-Mills fields blow-up in 4D, proving certain configurations impossible.
problem Prohibiting specific configurations of Yang-Mills fields in 4D.
method Expanding connection forms on long cylinders, proving equations relating bubble and limit connections.
result Proves certain configurations of Yang-Mills fields in 4D are impossible.
Given samples from a population of individuals belonging to different types with unknown proportions, how do we estimate the probability of discovering a new type at the -th draw? This is a classical problem in statistics, commonly referred to as the missing mass estimation problem. Recent results by Ohannes…
We solve the multi-criteria benchmarking problem by formalizing it as a social choice problem and identifying conditions for meaningful rankings.
problem Aggregating multiple metrics into a single ranking for models in benchmarking problems.
method Formalizing multi-criteria benchmarking as a social choice problem and identifying sufficient conditions for meaningful rankings.
result We prove that meaningful multi-criteria benchmarking becomes possible under certain preference conditions (single-peaked, group-separable, distance-restricted).
Explains agent behavior through intended outcomes in reinforcement learning.
problem Proving impossibility of general post-hoc explanations in reinforcement learning.
method Derives local explanations based on intention for Q-function approximations, proving consistency with learned Q-values.
result Demonstrates the necessity of collecting information during training for accurate explanations.
Paper investigates learnability of OOD detection under various conditions.
problem Learnability of OOD detection under different scenarios.
method Investigates PAC learning theory, proves impossibility theorems, and provides necessary and sufficient conditions.
result Some conditions for learnability of OOD detection may not hold in practical scenarios.
We show that if a split link is obtained from a split link in by -Dehn surgery along a trivial knot , then the link is splittable. That is to say, it is impossible to obtain a split link from a split link via a non-trivial twisting. As its corollary, we completely determine when a trivial li…
No universal trading strategy exists due to mathematical impossibilities.
problem The impossibility of universally winning trading strategies in competitive markets.
method Three mathematical paradigms: measure-theoretic, No-Free-Lunch theorem, and adversarial Cantor diagonalization.
result No-arbitrage and free-lunch principles are mathematically precluded in competitive markets.
Paper investigates OOD detection learnability under various conditions.
problem Learnability of OOD detection under diverse and unknown test data.
method PAC learning theory applied to OOD detection, proving impossibility theorems and necessary conditions.
result Some conditions for learnability hold in practical scenarios.
New findings show local attributions can't be both robust and provide recourse.
problem Ensuring machine learning systems are accountable and provide actionable recourse options.
method Formal definition of recourse sensitivity and counterexamples for popular attribution methods.
result It is impossible for any single attribution method to be both robust and provide recourse.
Investigates VaR behavior for sums of one-sided random variables, showing impossibilities and conditions for super-additivity.
problem Investigates the behavior of Value-at-Risk (VaR) for sums of one-sided random variables.
method Analyzes the extremal aggregation behavior of VaR, introduces structural conditions for super-additivity.
result Characterizes when VaR is fully super-additive and provides unified framework for various dependence structures.
We consider the problem of recovering a common latent source with independent components from multiple views. This applies to settings in which a variable is measured with multiple experimental modalities, and where the goal is to synthesize the disparate measurements into a single unified representation. We consider t…
Detecting correlated trees helps align sparse graphs.
problem Detecting correlation between trees for sparse random graphs.
method MPAlign message-passing algorithm for graph alignment.
result MPAlign succeeds in polynomial time for partial alignment.
Unobserved confounding is a central barrier to drawing causal inferences from observational data. Several authors have recently proposed that this barrier can be overcome in the case where one attempts to infer the effects of several variables simultaneously. In this paper, we present two simple, analytical counterexam…
Predicting the runtime complexity of a programming code is an arduous task. In fact, even for humans, it requires a subtle analysis and comprehensive knowledge of algorithms to predict time complexity with high fidelity, given any code. As per Turing's Halting problem proof, estimating code complexity is mathematically…
New research shows fair data representations are impossible for different tasks.
problem Achieving fairness in machine learning models trained on various tasks.
method Analyzing the limits of fair data representations.
result No representation can guarantee fairness for different tasks trained on it.
New findings show invariance alone isn't enough to identify latent causal variables.
problem Lack of theoretical insights for identifying latent causal variables when variables are latent.
method Assessed the connection between invariance and causal representation learning using impossibility results.
result Invariance alone is insufficient to identify latent causal variables.
Bell's theorem shows quantum correlations can't be explained by classical causal models, even with some measurement dependence.
problem Quantum correlations violate classical causal models.
method Using causal networks, the study bounds the level of measurement dependence and derives nonlinear Bell inequalities.
result Quantum correlations can't be explained by classical causal models even with some measurement dependence.
Nonconvex optimization algorithms with random initialization have attracted increasing attention recently. It has been showed that many first-order methods always avoid saddle points with random starting points. In this paper, we answer a question: can the nonconvex heavy-ball algorithms with random initialization avoi…
We study the fundamental limits of detecting the presence of an additive rank-one perturbation, or spike, to a Wigner matrix. When the spike comes from a prior that is i.i.d. across coordinates, we prove that the log-likelihood ratio of the spiked model against the non-spiked one is asymptotically normal below a certai…
Kleinberg introduced three natural clustering properties, or axioms, and showed they cannot be simultaneously satisfied by any clustering algorithm. We present a new clustering property, Monotonic Consistency, which avoids the well-known problematic behaviour of Kleinberg's Consistency axiom, and the impossibility resu…
Information theory plays an indispensable role in the development of algorithm-independent impossibility results, both for communication problems and for seemingly distinct areas such as statistics and machine learning. While numerous information-theoretic tools have been proposed for this purpose, the oldest one remai…