LCNs use Lovasz embeddings to capture global graph properties.
problem Semi-supervised learning on graph data.
method LCNs use Lovasz embeddings to incorporate global graph properties.
result LCNs outperform GCNs on various graph models and real-world datasets.
Novel convex surrogate for submodular losses with tractable computation.
problem Learning with non-modular losses for set prediction.
method Proposed Lovász hinge loss function for submodular losses.
result First tractable convex surrogates for submodular losses.
Paper develops privacy-preserving algorithms for online submodular optimization.
problem Online submodular optimization under differential privacy constraints.
method Develops algorithms for both full information and bandit feedback settings, using Lovasz extensions and unbiased estimates.
result Achieves low expected regret with differential privacy guarantees in both settings.
We extend the recently introduced theory of Lovasz-Bregman (LB) divergences (Iyer & Bilmes 2012) in several ways. We show that they represent a distortion between a "score" and an "ordering", thus providing a new view of rank aggregation and order based clustering with interesting connections to web ranking. We show ho…
We extend the recently introduced theory of Lovasz-Bregman (LB) divergences (Iyer & Bilmes, 2012) in several ways. We show that they represent a distortion between a 'score' and an 'ordering', thus providing a new view of rank aggregation and order based clustering with interesting connections to web ranking. We show h…
A key problem in statistics and machine learning is the determination of network structure from data. We consider the case where the structure of the graph to be reconstructed is known to be scale-free. We show that in such cases it is natural to formulate structured sparsity inducing priors using submodular functions,…
We introduce a new and rich class of graph coloring manifolds via the Hom complex construction of Lovasz. The class comprises examples of Stiefel manifolds, series of spheres and products of spheres, cubical surfaces, as well as examples of Seifert manifolds. Asymptotically, graph coloring manifolds provide examples of…
We consider a class of sparsity-inducing regularization terms based on submodular functions. While previous work has focused on non-decreasing functions, we explore symmetric submodular functions and their \lova extensions. We show that the Lovasz extension may be seen as the convex envelope of a function that depends …
Paper proposes a new method to minimize submodular functions with fewer calls to simpler oracles.
problem Minimizing the sum of submodular set functions with limited information.
method Introduces a modified convex problem requiring constrained total variation oracles that can be solved with fewer calls to minimization oracles.
result Shows significant reduction in the number of calls to minimization oracles.
We prove Csorba's conjecture that the Lovász complex Hom(C_5,K_n) of graph multimorphisms from the 5-cycle C_5 to the complete graph K_n is Z/2Z-equivariantly homeomorphic to the Stiefel manifold, V(n-1,2), the space of (ordered) orthonormal 2-frames in R^{n-1}. The equivariant piecewise-linear topology that we need is…
Characterizes 3D embeddability of certain 2D complexes via excluded minors.
problem Characterizing embeddability of specific 2D complexes in 3-space.
method Using Kuratowski-type characterisation via excluded minors.
result Answers Lovász, Pardon, and Wagner's questions about embeddability.
The detection of anomalous activity in graphs is a statistical problem that arises in many applications, such as network surveillance, disease outbreak detection, and activity monitoring in social networks. Beyond its wide applicability, graph structured anomaly detection serves as a case study in the difficulty of bal…
The paper introduces a method to decorrelate circular coordinates using lattice reduction.
problem Geometric correlation between circle-valued maps when multiple cohomology classes are used.
method Systematic procedure using the Lenstra--Lenstra--Lovász algorithm for constructing low energy torus-valued maps.
result A method to obtain less correlated maps from cohomology classes using integer linear combinations.
We extend several Cheeger-type isoperimetric bounds for convex sets in Euclidean space, due to Bobkov and Kannan-Lovász-Simonovits, to Riemannian manifolds having non-negative Ricci curvature. In order to extend Bobkov's bound, we require in addition an upper bound on the sectional curvature of the space, which permits…
The paper derives upper hedging prices for multivariate contingent claims using game-theoretic probability and submodularity.
problem Deriving upper hedging prices for complex financial contracts.
method Game-theoretic approach, optimization over simplexes, Lovász extension, Black-Scholes-Barenblatt equations.
result Upper and lower hedging prices can be calculated efficiently for submodular or supermodular payoff functions.
Unified solution to Goodman-Pollack transversal problem using matroids and topology.
problem Existence of an affine k-dimensional transversal to convex sets.
method Matroidal joins and topological methods.
result Unified solution including colorful Helly theorem and Holmsen's theorem.
New simplicial complexes show unavoidable link of spheres in high dimensions.
problem Finding unavoidable links of spheres in high-dimensional spaces.
method Simple argument in piecewise linear topology and application of the van Kampen--Flores theorem.
result Existence of additional simplicial complexes with unavoidable links of spheres.
The study characterizes embeddable 2-complexes in 3-space.
problem Characterizing embeddable 2-dimensional simplicial complexes in 3-space.
method Characterization through excluded minors and extensions.
result Characterized embeddable 2-complexes in 3-space, including cones over K5 and K3,3, and related constructions. LNMC improves link prediction on social networks by considering log-normal degree distributions.
problem Link prediction in social networks with log-normal degree distributions.
method Log-Normal Matrix Completion (LNMC) using Alternating Direction Method of Multipliers.
result Up to 5% AUC increase over non-structured sparsity based methods.
Algorithm learns CNF formulas from random solutions under specific conditions.
problem Learning a CNF formula from uniform random solutions.
method Revisits Valiant's algorithm and applies Lovász local lemma conditions.
result Significantly reduces sample complexity for learning CNFs.
Topology helps estimate chromatic numbers of random graphs on spheres.
problem Estimating chromatic numbers of random graphs on spheres.
method Topology, specifically connectivity of Lóvasz's neighborhood complex.
result Connectivity bound is useful in dimensions 1 and 2, but generally poor.
Deep learning improves salt deposits segmentation in seismic data.
problem Segmenting salt deposits in seismic reflection data for hydrocarbon exploration.
method A novel deep learning approach combining U-Net with ResNeXt-50 encoder, Spatial-Channel Squeeze & Excitation, Lovasz loss, CoordConv, and Hypercolumn methods.
result Achieved 27th place in Kaggle competition for salt deposits segmentation.
Universal tester-learner for halfspaces over structured distributions.
problem Learning halfspaces over a wide class of structured distributions.
method Uses a fully polynomial tester-learner based on hypercontractivity and sum-of-squares (SOS) programs.
result Achieves error O(opt)+ε on any labeled distribution that the tester accepts. Efficiently poisons offline RLHF models by flipping preference labels.
problem Vulnerability of offline RLHF models to preference label flipping attacks.
method Developed two attack methods: BAL-A and BMP-A, solving a structured binary sparse approximation problem.
result Demonstrated that flipping one preference label induces a parameter-independent shift in the DPO gradient, enabling structured binary sparse approximation.
New technique connects graph matching complexes to Morse theory for better topology understanding.
problem Understanding the topology of matching complexes of complete graphs.
method Developed discrete Morse theory technique to analyze Mn. result Showed Mn is geometrically (νn−1)-connected, improving on previous homotopical results. Faster algorithm for sampling logconcave densities in high dimensions.
problem Cubic barrier in sampling logconcave densities from a cold start.
method Two key ingredients: weaker distance sampling and refined log-Sobolev inequality.
result First sub-cubic sampling algorithms for isotropic position.
A graph (digraph) G=(V,E) with a set T⊆V of terminals is called inner Eulerian if each nonterminal node v has even degree (resp. the numbers of edges entering and leaving v are equal). Cherkassky and Lovász showed that the maximum number of pairwise edge-disjoint T-paths in an inner Eulerian graph $G…
CNN improves salt body interpretation in seismic imaging.
problem Manual salt body interpretation is time-consuming and prone to bias.
method U-Net and ResNet with ELU activation and Lovász-Softmax loss.
result CNN predictions match manual interpretations well, especially in weak reflection areas.
New algorithm recovers high-dimensional linear regression vectors without sparsity assumptions.
problem Efficiently recovering unknown vector β* from noisy linear observations in high dimensions.
method Proposes a polynomial-time algorithm based on LLL lattice basis reduction assuming rational entries with the same denominator.
result Algorithm successfully recovers β* for a large class of distributions and non-zero noise, even with small noise and one observation.
New constructions from non-separating planar graphs improve understanding of graph linkability and knotability.
problem Understanding linkability and knotability of graph complements.
method Using maximal non-separating planar graphs to construct examples of maximal linkless and knotless graphs, and analyzing their Colin de Verdière invariant.
result The Colin de Verdière invariant of the complement of a maximal non-separating planar graph satisfies μ(cG) ≤ n-4, and equality holds.
Polynomial-time algorithm finds planted hypercube vectors in Gaussian mixtures.
problem Clustering d-dimensional Gaussian mixtures with unknown covariance.
method Lattice-based methods using Lenstra--Lenstra--Lovasz reduction.
result Achieves statistically-optimal sample complexity of d+1 samples.
The study examines convergence of stochastic processes on large graphs and adjacency matrices.
problem Analyzing convergence of stochastic processes on large graphs and adjacency matrices.
method Introduced new metrics on the space of measure-valued graphons and used them to show convergence of random trajectories to deterministic curves.
result The Metropolis chain converges to a deterministic gradient flow curve on the space of graphons under certain conditions.
Reduces learning periodic neural networks to lattice problems, proving hardness under cryptographic assumptions.
problem Learning single periodic neurons in noisy environments.
method Reduction to worst-case lattice problems, using LLL algorithm.
result Polynomial-time algorithms for learning these functions are hard under cryptographic assumptions.
New spectral conditions ensure graph rigidity and global rigidity in the Euclidean plane.
problem Ensuring graph rigidity and global rigidity in the Euclidean plane.
method Improving algebraic connectivity bounds for graph rigidity and global rigidity.
result Every 6-connected graph is rigid and globally rigid if its algebraic connectivity exceeds specific thresholds.
The paper develops efficient algorithms for sampling from random spanning trees and determinantal point processes.
problem Sampling from strongly Rayleigh distributions efficiently.
method Optimal sublinear sampling algorithms for random spanning trees and determinantal point processes.
result Achieves optimal sublinear sampling for strongly Rayleigh distributions.
Extension formulae on almost complex manifolds studied with applications.
problem Understanding almost complex manifolds through extension formulae.
method Provided extension formulae and decompositions for almost complex manifolds.
result Studied (n,0)-forms, (n,0)-Dolbeault cohomology group, and (n,q)-forms. The paper proves extension theorems for holomorphic sections from divisors.
problem Extension of holomorphic sections from reduced unions of strata of divisors.
method Proves an Ohsawa--Takegoshi type extension theorem.
result Qualitative results on extension from snc divisors and generic global generation of vector bundles.
Generalizes Nielsen equivalence theorem to hyperbolic group extensions.
problem Tackles Nielsen equivalence in hyperbolic group extensions.
method Generalizes a theorem by Juan Souto to a broader class of hyperbolic extensions.
result Includes all hyperbolic extensions of surfaces groups and free groups by Out$(F_n).
The paper connects group extensions, cochains, and spectral sequences.
problem Understanding the relationship between group extensions and spectral sequences.
method Using connection cochains, the paper derives a formula for the extension class.
result A formula clarifies the relation among connection cochains, extension classes, and the LHS spectral sequence.
Proves HNN extensions of nilpotent groups are left-orderable, constructs non-left-orderable examples.
problem Characterizing left-orderability in HNN extensions of groups.
method Analyzes HNN extensions of torsion-free nilpotent groups and left-orderable groups.
result Constructs examples of non-left-orderable HNN extensions of left-orderable groups.
Paper analyzes mathematical theory behind out-of-sample DR extensions.
problem Developing a solid mathematical foundation for out-of-sample DR extensions.
method Utilizes RKHS theory to treat DR extension as an extension of the identity on RKHS defined on X.
result Shows Nyström-type DR extension as an orthogonal projection and provides conditions for exact DR extension.
Examines differential smoothness in a specific skew PBW extension family.
problem Differential smoothness in skew PBW extensions.
method Investigates a specific family of skew PBW extensions.
result Results on differential smoothness of the family.
New insights into identifying mixtures of product distributions using Hadamard extensions.
problem Identifying mixtures of product distributions on binary variables.
method Analysis of Hadamard extensions of matrix products.
result Conditions for full column rank of Hadamard extensions.
A spacetime can be embedded in an enveloping space with all its extensions.
problem Existence and uniqueness of C0-maximal extensions in globally hyperbolic conformally flat spacetimes.
method Proving conformal embedding into an enveloping space containing all extensions.
result Existence and uniqueness of C0-maximal extensions proven.
We generalize the prequantization central extension of a group of diffeomorphisms preserving a closed 2-form ω(ω-invariant diffeomorphisms) to an abelian extension of a group of diffeomorphisms preserving a closed vector valued 2-form ω, up to a linear isomorphism (ω-equivariant diffeomorphisms). Every abelian extensio…
We give a new variant of L2-extension theorem for the jets of holomorphic sections and discuss the relation between the extension problem of singular Hermitian metrics with semipositive curvature.
Study on flux homomorphism and its extension in symplectic group of a disk.
problem Understanding the flux homomorphism and its extension in symplectic group.
method Defined and analyzed the flux homomorphism and its extension, determined the Euler class, and investigated its relation to group 2-cocycle and Calabi invariant.
result Determined the Euler class of the flux extension and investigated its relation to group 2-cocycle and Calabi invariant.
The purpose of this paper is to show how central extensions of (possibly infinite-dimensional) Lie algebras integrate to central extensions of étale Lie 2-groups. In finite dimensions, central extensions of Lie algebras integrate to central extensions of Lie groups, a fact which is due to the vanishing of π_2 for each …