An official website of the United States government
We study the problem of fair k-median where each cluster is required to have a fair representation of individuals from different groups. In the fair representation k-median problem, we are given a set of points X in a metric space. Each point x ∈ X belongs to one of ℓ groups. Further, we are given fair representation parameters αj and β_j for each group j ∈ [ℓ]. We say that a k-clustering C_1, ⋅⋅⋅, C_k fairly represents all groups if the number of points from group j in cluster C_i is between α_j |C_i| and β_j |C_i| for every j ∈ [ℓ] and i ∈ [k]. The goal is to find a set of k centers and an assignment such that the clustering defined by fairly represents all groups and minimizes the ℓ_1-objective ∑_{x ∈ X} d(x, ϕ(x)). We present an O(log k)-approximation algorithm that runs in time n^{O(ℓ)}. Note that the known algorithms for the problem either (i) violate the fairness constraints by an additive term or (ii) run in time that is exponential in both k and ℓ. We also consider an important special case of the problem where and for all j ∈ [ℓ]. For this special case, we present an O(log k)-approximation algorithm that runs in time.
more »
« less
Cup products on curves over finite fields
In this paper we compute cup products of elements of the first étale cohomology group of μℓ over a smooth projective geometrically irreducible curve C over a finite field k when ℓ is a prime and #k≡1 mod ℓ. Over the algebraic closure of k, such products are values of the Weil pairing on the ℓ-torsion of the Jacobian of C. Over k, such cup products are more subtle due to the fact that they naturally take values in Pic(C)⊗Zμ~ℓ rather than in the group μ~ℓ of ℓth roots of unity in k∗.
more »
« less
- Award ID(s):
- 1701785
- PAR ID:
- 10382884
- Date Published:
- Journal Name:
- arXivorg
- ISSN:
- 2331-8422
- Page Range / eLocation ID:
- arXiv:2101.00329
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)Abstract We construct a $$(\mathfrak {gl}_2, B(\mathbb {Q}_p))$$ and Hecke-equivariant cup product pairing between overconvergent modular forms and the local cohomology at $$0$$ of a sheaf on $$\mathbb {P}^1$$ , landing in the compactly supported completed $$\mathbb {C}_p$$ -cohomology of the modular curve. The local cohomology group is a highest-weight Verma module, and the cup product is non-trivial on a highest-weight vector for any overconvergent modular form of infinitesimal weight not equal to $$1$$ . For classical weight $$k\geq 2$$ , the Verma has an algebraic quotient $$H^1(\mathbb {P}^1, \mathcal {O}(-k))$$ , and on classical forms, the pairing factors through this quotient, giving a geometric description of ‘half’ of the locally algebraic vectors in completed cohomology; the other half is described by a pairing with the roles of $H^1$ and $H^0$ reversed between the modular curve and $$\mathbb {P}^1$$ . Under minor assumptions, we deduce a conjecture of Gouvea on the Hodge-Tate-Sen weights of Galois representations attached to overconvergent modular forms. Our main results are essentially a strict subset of those obtained independently by Lue Pan, but the perspective here is different, and the proofs are short and use simple tools: a Mayer-Vietoris cover, a cup product, and a boundary map in group cohomology.more » « less
-
Abstract One-dimensional persistent homology is arguably the most important and heavily used computational tool in topological data analysis. Additional information can be extracted from datasets by studying multi-dimensional persistence modules and by utilizing cohomological ideas, e.g. the cohomological cup product. In this work, given a single parameter filtration, we investigate a certain 2-dimensional persistence module structure associated with persistent cohomology, where one parameter is the cup-length$$\ell \ge 0$$ and the other is the filtration parameter. This new persistence structure, called thepersistent cup module, is induced by the cohomological cup product and adapted to the persistence setting. Furthermore, we show that this persistence structure is stable. By fixing the cup-length parameter$$\ell $$ , we obtain a 1-dimensional persistence module, called the persistent$$\ell $$ -cup module, and again show it is stable in the interleaving distance sense, and study their associated generalized persistence diagrams. In addition, we consider a generalized notion of apersistent invariant, which extends both therank invariant(also referred to aspersistent Betti number), Puuska’s rank invariant induced by epi-mono-preserving invariants of abelian categories, and the recently-definedpersistent cup-length invariant, and we establish their stability. This generalized notion of persistent invariant also enables us to lift the Lyusternik-Schnirelmann (LS) category of topological spaces to a novel stable persistent invariant of filtrations, called thepersistent LS-category invariant.more » « less
-
The modular group algebra of an elementary abelian p-group is isomorphic to the restricted enveloping algebra of a commutative restricted Lie algebra. The different ways of regarding this algebra result in different Hopf algebra structures that determine cup products on cohomology of modules. However, it is proved in this paper that the products with elements of the polynomial subring of the cohomology ring generated by the Bocksteins of the degree one elements are independent of the choice of these coalgebra structures.more » « less
-
Guruswami, Venkatesan (Ed.)Recent efforts in Analysis of Boolean Functions aim to extend core results to new spaces, including to the slice binom([n],k), the hypergrid [K]ⁿ, and noncommutative spaces (matrix algebras). We present here a new way to relate functions on the hypergrid (or products of cyclic groups) to their harmonic extensions over the polytorus. We show the supremum of a function f over products of the cyclic group {exp(2π i k/K)}_{k = 1}^K controls the supremum of f over the entire polytorus ({z ∈ ℂ:|z| = 1}ⁿ), with multiplicative constant C depending on K and deg(f) only. This Remez-type inequality appears to be the first such estimate that is dimension-free (i.e., C does not depend on n). This dimension-free Remez-type inequality removes the main technical barrier to giving 𝒪(log n) sample complexity, polytime algorithms for learning low-degree polynomials on the hypergrid and low-degree observables on level-K qudit systems. In particular, our dimension-free Remez inequality implies new Bohnenblust-Hille-type estimates which are central to the learning algorithms and appear unobtainable via standard techniques. Thus we extend to new spaces a recent line of work [Eskenazis and Ivanisvili, 2022; Huang et al., 2022; Volberg and Zhang, 2023] that gave similarly efficient methods for learning low-degree polynomials on the hypercube and observables on qubits. An additional product of these efforts is a new class of distributions over which arbitrary quantum observables are well-approximated by their low-degree truncations - a phenomenon that greatly extends the reach of low-degree learning in quantum science [Huang et al., 2022].more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- The DOI is not currently available.
