Survey on complex submanifolds in Euclidean spaces.
problem Existence of complete bounded complex submanifolds.
method Historical overview and recent progress.
result Discussion of open questions in the field.
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,742 papers · 148 categories
Trend · papers per month
48 results for “problem complexity”
In this paper we prove the probabilistic continuous complexity conjecture. In continuous complexity theory, this states that the complexity of solving a continuous problem with probability approaching 1 converges (in this limit) to the complexity of solving the same problem in its worst case. We prove the conjecture ho…
Researchers show a complex structure is not a counterexample to a topological problem.
problem Wall's D2 problem about finite CW-complexes.
method Introduced and analyzed new presentations of quaternion groups to prove homotopy types.
result The complex structure is not a counterexample to Wall's D2 problem.
Open problem: fixed-budget best arm identification complexity.
problem Understanding the complexity of identifying the best arm in a fixed budget setting.
method Analyzing existing results and conjectures in the fixed-confidence setting.
result Open questions remain about the fixed-budget setting.
We survey results about computational complexity of the word problem in groups, Dehn functions of groups and related problems.
We show that the genus problem for alternating knots with crossings has linear time complexity and is in Logspace. Almost all alternating knots of given genus possess additional combinatorial structure, we call them standard. We show that the genus problem for these knots belongs to circuit complexity c…
PURE-CD algorithm proves complexity bounds for convex-concave problems.
problem Solving convex-concave min-max problems with bilinear coupling.
method Primal-dual algorithm with random extrapolation and coordinate descent (PURE-CD).
result Complexity bounds match or improve existing results for dense and sparse problems.
Solves a 60-year-old compatibility problem on manifolds with boundary.
problem Finding a compatibility operator for Lie derivatives of the metric tensor on compact Riemannian manifolds.
method Develops a framework for elliptic pre-complexes and pseudodifferential operators to correct and yield Hodge-like decompositions.
result Explicit integrability conditions for overdetermined boundary-value problems are derived, resolving the Saint-Venant problem.
Survey on rational curves on complex surfaces, highlighting different approaches.
problem Existence of rational curves on complex surfaces.
method Classification of complex surfaces and systematic study of rational curves in each class.
result Highlighting the different approaches to study rational curves on complex surfaces.
Survey on 3-manifold problems and their complexity.
problem Decision problems in 3-manifold theory.
method Tools like normal surfaces, hierarchies, homomorphisms, and hyperbolic structures.
result Discussion of computational complexity of 3-manifold problems.
We investigate the average-case complexity of decision problems for finitely generated groups, in particular the word and membership problems. Using our recent results on ``generic-case complexity'' we show that if a finitely generated group has the word problem solvable in subexponential time and has a subgroup of…
Study proposes a functional for LCK metrics on complex manifolds.
problem Existence problem for locally conformally Kähler metrics on compact complex manifolds.
method Introducing and studying a functional that varies by complex dimension.
result Functional approach to existence problem for LCK metrics.
Paper proposes an algorithm to solve complex minimax problems efficiently.
problem Stochastic nonconvex-concave minimax problems in various fields.
method Accelerated first-order regularized momentum descent ascent algorithm (FORMDA).
result Achieves best-known complexity bound of for single-loop algorithms.
Paper solves open problem in complex Finsler geometry.
problem Existence of non-Kähler weakly Kähler Finsler metrics.
method Constructs a family of weakly Kähler Finsler metrics.
result Proves uniformization theorem for unitary invariant complex Randers metrics.
New findings show Rademacher complexities are not crucial for learning complexities.
problem Understanding the sample complexity of learning with squared loss in convex classes.
method Novel learning procedure combining mean estimation and Talagrand's generic chaining method.
result Sample complexity is determined by the limiting Gaussian process, not Rademacher complexities.
Proves Hölder continuity of complex Monge-Ampère solutions.
problem Global Hölder continuity of solutions to complex Monge-Ampère equation.
method Analyzes Dirichlet problem on strictly pseudoconvex domains or Hermitian manifolds.
result Proves global Hölder continuity of solutions under given conditions.
Paper addresses quadratic feasibility problems and their sample complexity.
problem Recovering complex vectors from quadratic measurements.
method Analyzes conditions for identifiability and explores optimization landscape.
result Gradient algorithms can converge to globally optimal solutions with high probability.
Minimal genus surfaces solve homology problems in finite complexes.
problem Finding surface representatives of homology classes with minimal genus.
method Minimizing genus and Euler characteristic, analyzing surgeries and homotopy.
result Minimizers are homotopic to cellwise coverings, but problem is undecidable in general.
The Sample Complexity of Distributed Simple Binary Hypothesis Testing under Information Constraintscs.IT
Paper resolves open problems on sample complexity in binary hypothesis testing.
problem Open problems in distributed simple binary hypothesis testing under information constraints.
method One-shot lower bound on Bayes error, streamlined sample complexity formula, reverse data-processing inequality.
result Optimally tight sample complexity bounds for communication-constrained simple binary hypothesis testing.
The Chern-Ricci flowmath.DG
Survey on Chern-Ricci flow for complex manifolds.
problem Understanding and solving open problems in Chern-Ricci flow.
method Parabolic flow of Hermitian metrics on complex manifolds.
result Open problems and new directions in Chern-Ricci flow highlighted.
Improved Sinkhorn algorithm for UOT with near-linear complexity.
problem Solving the entropic regularized Unbalanced Optimal Transport problem efficiently.
method Geometric convergence analysis of Sinkhorn updates and primal solution properties.
result Near-linear time complexity for finding -approximate UOT solutions.
Investigates regularity of solutions to complex Hessian equation.
problem Regularity of solutions to complex Hessian equation.
method Analyzes solutions to Dirichlet problem with specific density condition.
result Establishes conditions for regularity of solutions.
In this paper, we solve in the negative the following problem : Is there any complex structure on the sphere S^6?
Learning bounded subsets of stat.ML
Sharp sample complexity for learning bounded subsets.
problem Learning bounded subsets of with .
method Heavy-tailed learning procedure.
result Sharp sample complexity estimate for any .
No free lunch theorems suggest inductive biases are needed, but we show neural networks prefer low-complexity data.
problem The need for inductive biases in machine learning.
method Analysis of Kolmogorov complexity and neural network behavior on various datasets.
result Neural networks prefer low-complexity data, suggesting inductive biases are not always necessary.
In this paper we consider several classical and novel algorithmic problems for right-angled Artin groups, some of which are closely related to graph theoretic problems, and study their computational complexity. We study these problems with a view towards applications to cryptography.
We present a family of complexes playing the same role, for homogeneous variational problems, that the horizontal parts of the variational bicomplex play for variational problems on a fibred manifold. We show that, modulo certain pullbacks, each of these complexes (apart from the first one) is globally exact. All the c…
The article resolves complex structures in transport twistor spaces, proving a Newlander-Nirenberg theorem.
problem Degenerate complex structures in transport twistor spaces.
method Holomorphic blow-down structure maps to resolve degeneracy and gain insight into complex geometry.
result Global and local β-maps for various metrics, proving a Newlander-Nirenberg theorem for degenerate complex structures.
Improved complexity for smooth nonconvex optimization using quasi-Newton methods.
problem Finding ε-first-order stationary points of smooth functions with gradient information only.
method Two-level online learning approach involving quasi-Newton methods.
result Gradient complexity improved to O(d^(1/4)ε^(-13/8)) for d = O(ε^(-1/2)).
A General Framework for Complex Network Applicationsphysics.soc-ph
Complex network theory has been applied to solving practical problems from different domains. In this paper, we present a general framework for complex network applications. The keys of a successful application are a thorough understanding of the real system and a correct mapping of complex network theory to practical …
Lower bound for complexity of finding flex points on cubic curves.
problem Finding flex points on cubic plane curves.
method Bounding the Schwarz genus of a cover associated to the problem.
result Lower bound for topological complexity close to optimal.
Improved zeroth-order algorithms tackle nonconvex minimax problems with reduced complexity.
problem Nonconvex minimax optimization problems in machine learning.
method Design and analysis of Zeroth-Order Gradient Descent Ascent ( exttt{ZO-GDA}) and Zeroth-Order Gradient Descent Multi-Step Ascent ( exttt{ZO-GDMSA}) algorithms.
result Oracle complexity improvements for minimax optimization problems.
Study solves complex equation on specific types of manifolds.
problem Solving complex Monge-Ampère equation on Kähler manifolds.
method Flow-based arguments to establish existence of smooth solutions.
result Existence of smooth solutions under decreasing right-hand side.
The SPS method constructs confidence regions for true parameters with optimal sample complexity.
problem Constructing exact, non-asymptotic confidence regions for true system parameters.
method Sign-Perturbed Sums (SPS) method, generalized to various types of problems.
result High probability upper bounds for SPS confidence regions show optimal shrinkage rate.
Note on the computational complexity of Gromov-Wasserstein distance.
problem Computational difficulty of Gromov-Wasserstein distance.
method Analysis of the optimization problem structure and providing explicit examples.
result Gromov-Wasserstein distance optimization problem is non-convex quadratic.
Private optimization faster on interpolation problems with quadratic growth.
problem Private optimization in interpolation problems.
method Adaptive algorithm with improved sample complexity.
result Exponential improvement in private sample complexity for quadratic growth.
2-dimensional Kähler-Einstein metrics induced by finite dimensional complex projective spacesmath.DG
Solves classical problem with Kähler-Einstein metrics in complex projective spaces.
problem Classical problem of non-isometric bidimensional Kähler-Einstein submanifolds.
method Listed complete non-isometric bidimensional rotation invariant Kähler-Einstein submanifolds.
result Solves the classical problem in the specified case.
Paper proves conditions for rational homology complex projective planes with singularities.
problem Proving conditions for rational homology complex projective planes with singularities.
method Leveraging results from smooth 4-manifolds, including Donaldson diagonalization theorem and Heegaard Floer correction terms.
result Eliminates the possibility of a rational homology complex projective plane with four singularities and identifies families of singularities obstructed by smooth conditions.
We consider computational complexity of problems related to the fundamental group and the first homology group of (embeddable) -complexes. We show, as an extension of an earlier work, that computing first homology of -complexes is equivalent in computational complexity to matrix diagonalization. That is, the usua…
Study on Hölder continuity of complex Monge-Ampère solutions on Stein spaces.
problem Understanding continuity of solutions to complex Monge-Ampère equations on Stein spaces.
method Analyzing solutions with densities and Hölder boundary data on Stein spaces with isolated singularities.
result Solutions are Hölder continuous outside singular points if boundary data is Hölder continuous.
Characteristics extracted from the training datasets of classification problems have proven to be effective predictors in a number of meta-analyses. Among them, measures of classification complexity can be used to estimate the difficulty in separating the data points into their expected classes. Descriptors of the spat…
We propose a list of open problems in pluripotential theory partially motivated by their applications to complex differential geometry. The list includes both local questions as well as issues related to the compact complex manifold setting.
We prove a general connection between the communication complexity of two-player games and the sample complexity of their multi-player locally private analogues. We use this connection to prove sample complexity lower bounds for locally differentially private protocols as straightforward corollaries of results from com…
First Chen Inequality for CR-Warped Product Submanifolds of a Complex Space Form and Applicationsmath.DG
The paper proves a new inequality for CR-warped product submanifolds in complex space forms.
problem Proving a new inequality for CR-warped product submanifolds in complex space forms.
method Developed a first Chen inequality for CR-warped product submanifolds in complex space forms.
result The bound is sharp and uniform in the sign of the holomorphic sectional curvature.
The existence of some complex geometrical structures on a compact manifold such as complex structures, Kaehler (pseudo-Kaehler) structures often impose certain restrictions on its underling topological or differentiable manifold. In this article we survey recent developments in the study of the existence, classificatio…
Study on eigenvalues of complex Hessian operator on pseudoconvex manifolds.
problem Eigenvalue problem for complex Hessian operator on pseudoconvex manifolds.
method Established -regularity and uniqueness of the first eigenfunction, derived variational formula for the first eigenvalue.
result Derivation of a bifurcation-type theorem and geometric bounds for the eigenvalue.
Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noisecs.LG
Study shows a tradeoff between sample complexity and computational efficiency for learning halfspaces with random noise.
problem PAC learning γ-margin halfspaces with Random Classification Noise.
method Established an information-computation tradeoff and provided a simple efficient algorithm with sample complexity O(1/(γ^2 ε^2)). Also, proved lower bounds for SQ algorithms and low-degree polynomial tests.
result Inherent gap between sample complexity and computational efficiency for learning halfspaces with random noise.
A new algorithm reduces the complexity of solving optimal transport problems.
problem Optimal transport problem with linear constraints.
method Primal-dual accelerated stochastic gradient descent with variance reduction (PDASGD).
result Achieves the best-known computational complexity of for OT problems.