More Like this

1. Linear Thompson Sampling Under Unknown Linear Constraints

   https://doi.org/10.1109/ICASSP40776.2020.9053865  

   Moradipari, Ahmadreza; Alizadeh, Mahnoosh; Thrampoulidis, Christos (May 2020, ICASSP 2020)

   null (Ed.)
2. Supersaturation of even linear cycles in linear hypergraphs

   https://doi.org/10.1017/S0963548320000206  

   Jiang, Tao; Yepremyan, Liana (September 2020, Combinatorics, Probability and Computing)

   Abstract A classical result of Erdős and, independently, of Bondy and Simonovits [3] says that the maximum number of edges in ann-vertex graph not containingC_2k, the cycle of length 2k, isO(n^1+1/k). Simonovits established a corresponding supersaturation result forC_2k’s, showing that there exist positive constantsC,cdepending only onksuch that everyn-vertex graphGwithe(G)⩾Cn^1+1/kcontains at leastc(e(G)/v(G))^2kcopies ofC_2k, this number of copies tightly achieved by the random graph (up to a multiplicative constant). In this paper we extend Simonovits' result to a supersaturation result ofr-uniform linear cycles of even length inr-uniform linear hypergraphs. Our proof is self-contained and includes ther= 2 case. As an auxiliary tool, we develop a reduction lemma from general host graphs to almost-regular host graphs that can be used for other supersaturation problems, and may therefore be of independent interest. 

   more » « less
3. Speeding up Linear Programming using Randomized Linear Algebra

   Chowdhuri, Agniva; London, Palma; Avron, Haim; Drineas, Petros (January 2020, 34th Conference on Neural Information Processing Systems (NeurIPS))

   null (Ed.)
4. Coordinate Linear Variance Reduction for Generalized Linear Programming

   Song, Chaobing; Lin, Cheuk-Yin; Wright, Stephen; Diakonikolas, Jelena (December 2022, 36th Conference on Neural Information Processing Systems (NeurIPS 2022))
5. A Complete Linear Programming Hierarchy for Linear Codes

   https://doi.org/10.4230/LIPIcs.ITCS.2022.51  

   Coregliano, Leonardo Nagami (January 2022, Leibniz international proceedings in informatics)

   Braverman, Mark (Ed.)

   A longstanding open problem in coding theory is to determine the best (asymptotic) rate R₂(δ) of binary codes with minimum constant (relative) distance δ. An existential lower bound was given by Gilbert and Varshamov in the 1950s. On the impossibility side, in the 1970s McEliece, Rodemich, Rumsey and Welch (MRRW) proved an upper bound by analyzing Delsarte’s linear programs. To date these results remain the best known lower and upper bounds on R₂(δ) with no improvement even for the important class of linear codes. Asymptotically, these bounds differ by an exponential factor in the blocklength. In this work, we introduce a new hierarchy of linear programs (LPs) that converges to the true size A^{Lin}₂(n,d) of an optimum linear binary code (in fact, over any finite field) of a given blocklength n and distance d. This hierarchy has several notable features: 1) It is a natural generalization of the Delsarte LPs used in the first MRRW bound. 2) It is a hierarchy of linear programs rather than semi-definite programs potentially making it more amenable to theoretical analysis. 3) It is complete in the sense that the optimum code size can be retrieved from level O(n²). 4) It provides an answer in the form of a hierarchy (in larger dimensional spaces) to the question of how to cut Delsarte’s LP polytopes to approximate the true size of linear codes. We obtain our hierarchy by generalizing the Krawtchouk polynomials and MacWilliams inequalities to a suitable "higher-order" version taking into account interactions of 𝓁 words. Our method also generalizes to translation schemes under mild assumptions. 

   more » « less