Publications associées à Linear Programming Decoding of Spatially Coupled Codes

On Speed and Advantage : Results in Information Velocity and Monitoring Problems

Information theory has allowed us to determine the fundamental limit of various communication and algorithmic problems, e.g., the channel coding problem, the compression problem, and the hypothesis testing problem. In this work, we revisit the assumptions ...

EPFL2024

Learning to Remove Cuts in Integer Linear Programming

Volkan Cevher, Grigorios Chrysos, Efstratios Panteleimon Skoulakis

Cutting plane methods are a fundamental approach for solving integer linear programs (ILPs). In each iteration of such methods, additional linear constraints (cuts) are introduced to the constraint set with the aim of excluding the previous fractional opti ...

2024

A ride time-oriented scheduling algorithm for dial-a-ride problems

Nikolaos Geroliminis, Claudia Bongiovanni, Mor Kaspi

This paper offers a new algorithm to efficiently optimize scheduling decisions for dial-a-ride problems (DARPs), including problem variants considering electric and autonomous vehicles (e-ADARPs). The scheduling heuristic, based on linear programming theor ...

Pergamon-Elsevier Science Ltd2024

High-Throughput and Flexible Belief Propagation List Decoder for Polar Codes

Andreas Peter Burg, Alexios Konstantinos Balatsoukas Stimming, Chuan Zhang, Andreas Toftegaard Kristensen, Yifei Shen, Yuqing Ren

Due to its high parallelism, belief propagation (BP)decoding is amenable to high-throughput applications and thusrepresents a promising solution for the ultra-high peak datarate required by future communication systems. To bridge theperformance gap compare ...

Ieee-Inst Electrical Electronics Engineers Inc2024

Six-dimensional sphere packing and linear programming

Maryna Viazovska, Maria Margarethe Dostert, Matthew De Courcy-Ireland

We prove that the Cohn-Elkies linear programming bound for sphere packing is not sharp in dimension 6. The proof uses duality and optimization over a space of modular forms, generalizing a construction of Cohn- Triantafillou [Math. Comp. 91 (2021), pp. 491 ...

Amer Mathematical Soc2024

HYPERBOLA METHOD ON TORIC VARIETIES

Marta Pieropan

We develop a very general version of the hyperbola method which extends the known method by Blomer and Brudern for products of projective spaces to complete smooth split toric varieties. We use it to count Campana points of bounded log-anticanonical height ...

Ecole Polytechnique2024

Quantifying the Unknown: Data-Driven Approaches and Applications in Energy Systems

Paul Scharnhorst

In light of the challenges posed by climate change and the goals of the Paris Agreement, electricity generation is shifting to a more renewable and decentralized pattern, while the operation of systems like buildings is increasingly electrified. This calls ...

EPFL2024

A Spatial Branch and Bound Algorithm for Continuous Pricing with Advanced Discrete Choice Demand Modeling

Michel Bierlaire

In this paper, we present a spatial branch and bound algorithm to tackle the continuous pricing problem, where demand is captured by an advanced discrete choice model (DCM). Advanced DCMs, like mixed logit or latent class models, are capable of modeling de ...

2023

Scalable Metaprogramming in Scala 3

Nicolas Alexander Stucki

A metaprogrammer should be able to reason about the semantics of the generated code. Multi-stage programming introduced an elegant and powerful solution to this problem. It follows a semantically driven approach to code generation, where semantics are full ...

EPFL2023

Data-Driven Control and Optimization under Noisy and Uncertain Conditions

Baiwei Guo

Control systems operating in real-world environments often face disturbances arising from measurement noise and model mismatch. These factors can significantly impact the perfor- mance and safety of the system. In this thesis, we aim to leverage data to de ...

EPFL2023

GRAMM: Fast CGRA Application Mapping Based on A Heuristic for Finding Graph Minors

Mirjana Stojilovic, Guanglei Zhou

A graph H is a minor of a second graph G if G can be transformed into H by two operations: 1) deleting nodes and/or edges, or 2) contracting edges. Coarse-grained reconfigurable array (CGRA) application mapping is closely related to the graph minor problem ...

Los Alamitos2023

Symmetry in design and decoding of polar-like codes

Kirill Ivanov

The beginning of 21st century provided us with many answers about how to reach the channel capacity. Polarization and spatial coupling are two techniques for achieving the capacity of binary memoryless symmetric channels under low-complexity decoding algor ...

EPFL2022

On the Efficiency of Polar-Like Decoding for Symmetric Codes

Rüdiger Urbanke, Kirill Ivanov

The recently introduced polar codes constitute a breakthrough in coding theory due to their capacity-achieving property. This goes hand in hand with a quasilinear construction, encoding, and successive cancellation list decoding procedures based on the Plo ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022

Optima Age Over Erasure Channels

Emre Telatar, Rajai Nasser, Elie Najm

Previous works on age of information and erasure channels have dealt with specific models and computed the average age or average peak age for certain settings. In this paper, given a source that produces a letter every T-s seconds and an erasure channel t ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022

Relaxed Locally Correctable Codes With Nearly-Linear Block Length And Constant Query Complexity

Alessandro Chiesa

Locally correctable codes (LCCs) are error correcting codes C : \Sigmak \rightarrow \Sigman which admit local algorithms that correct any individual symbol of a corrupted codeword via a minuscule number of queries. For systematic codes, this notion is stro ...

SIAM PUBLICATIONS2022

List Ordered Statistics Decoders for Polar Codes

Andreas Peter Burg, Chuan Zhang, Yifei Shen

The de-facto standard decoding algorithm for polar codes, successive cancellation list (SCL) decoding, is a breadth-first search algorithm. By keeping a list of candidate codewords, SCL decoding improves the performance as the list size L increases. Howeve ...

IEEE2022

A Functional Perspective on Information Measures

Amedeo Roberto Esposito

Since the birth of Information Theory, researchers have defined and exploited various information measures, as well as endowed them with operational meanings. Some were born as a "solution to a problem", like Shannon's Entropy and Mutual Information. Other ...

EPFL2022

Fast Sequence Repetition Node-Based Successive Cancellation List Decoding for Polar Codes

Andreas Peter Burg, Alexios Konstantinos Balatsoukas Stimming, Chuan Zhang, Andreas Toftegaard Kristensen, Yifei Shen, Yuqing Ren

Compared with the bit-wise successive cancellation list (SCL) decoding of polar codes, the node-based Fast SCL decoding significantly reduces the decoding latency by identifying special constituent codes and decoding these in parallel. To further reduce th ...

IEEE2022

Removing Algorithmic Discrimination (With Minimal Individual Error)

Rachid Guerraoui, El Mahdi El Mhamdi, Le Nguyen Hoang, Alexandre David Olivier Maurer

We address for the first time the problem of correcting group discriminations within a score function, while minimizing the individual error. Each group is described by a probability density function on the set of profiles. We first solve the problem analy ...

2022

Secret Key Generation Using Short Blocklength Polar Coding Over Wireless Channels

Yanina Yurina Shkel

This paper investigates the problem of secret key generation from correlated Gaussian random variables in the short blocklength regime. Short blocklengths are commonly employed in massively connected IoT sensor networks in 5G and beyond wireless systems. P ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022