Concept

Big O notation

Related publications (72)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

No Small Linear Program Approximates Vertex Cover within a Factor 2 - e

Ola Nils Anders Svensson, Abbas Bazzi

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regevproved that the problem is NP-hard to approximate within a factor2 - ∈, assuming the Unique Games Conjecture (UGC). This is tig ...

IEEE Computer Society2015

Second-Order Rate Region of Constant-Composition Codes for the Multiple-Access Channel

Jonathan Mark Scarlett, Albert Guillén i Fàbregas

This paper studies the second-order asymptotics of coding rates for the discrete memoryless multiple-access channel (MAC) with a fixed target error probability. Using constant-composition random coding, coded time-sharing, and a variant of Hoeffding's comb ...

Ieee-Inst Electrical Electronics Engineers Inc2015

Second-order asymptotics for the Gaussian MAC with degraded message sets

Jonathan Mark Scarlett

This paper studies the second-order asymptotics of the Gaussian multiple-access channel with degraded message sets. For a fixed average error probability epsilon is an element of (0, 1) and an arbitrary point on the boundary of the capacity region, we char ...

Institute of Electrical and Electronics Engineers2015

Discrete stochastic heat equation driven by fractional noise

Kamran Kalbasi

We consider the parabolic Anderson model on

\mathbb{Z}^d

driven by fractional noise. We prove that it has a mild solution given by Feynman-Kac representation which coincides with the partition function of a directed polymer in a fractional Brownian envir ...

EPFL2014

Almost Polynomial Factor Hardness for Closest Vector Problem with Preprocessing

Nisheeth Vishnoi

We prove that for an arbitrarily small constant < 0, the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor 2log1-en, under the assumption that NP ⊈ SIZE(2logO(1/e)n). © 2014 Soc ...

Society for Industrial and Applied Mathematics2014

Linear Programming Decoding of Spatially Coupled Codes

Rüdiger Urbanke, Badih Ghazi

For a given family of spatially coupled codes, we prove that the linear programming (LP) threshold on the binary-symmetric channel (BSC) of the tail-biting graph cover ensemble is the same as the LP threshold on the BSC of the derived spatially coupled ens ...

Ieee-Inst Electrical Electronics Engineers Inc2014

Rate-Dependent Analysis of the Asymptotic Behavior of Channel Polarization

Rüdiger Urbanke, Seyed Hamed Hassani

We consider the asymptotic behavior of the polarization process in the large block-length regime when transmission takes place over a binary-input memoryless symmetric channel W. In particular, we study the asymptotics of the cumulative distribution, P(Z(n ...

Ieee-Inst Electrical Electronics Engineers Inc2013

Primeless Factoring-Based Cryptography

Serge Vaudenay, Sonia Mihaela Bogos

Factoring-based public-key cryptosystems have an overall complexity which is dominated by the key-production algorithm, which requires the generation of prime numbers. This is most inconvenient in settings where the key-generation is not an one-off process ...

2013

On Generalized Weighted Hilbert Matrices

Olivier Lévêque

We study spectral properties of generalized weighted Hilbert matrices. In particular, we establish results on the spectral norm, the determinant, and various relations between the eigenvalues and eigenvectors of such matrices. We also study the asymptotic ...

Pacific Journal Mathematics2013

Practicality and time complexity of a sparsified RNA folding algorithm

Philipp Bucher, Slavica Dimitrieva Janeva

Commonly used RNA folding programs compute the minimum free energy structure of a sequence under the pseudoknot exclusion constraint. They are based on Zuker's algorithm which runs in time O(n^3). Recently, it has been claimed that RNA folding can be achie ...

2012

Discrete stochastic heat equation driven by fractional noise

Kamran Kalbasi

We consider the parabolic Anderson model on

\mathbb{Z}^d

EPFL2014