Publications related to L-notation

Fast and Space Efficient Spectral Sparsification in Dynamic Streams

Mikhail Kapralov, Jakab Tardos, Navid Nouri, Aidasadat Mousavifar

In this paper, we resolve the complexity problem of spectral graph sparcification in dynamic streams up to polylogarithmic factors. Using a linear sketch we design a streaming algorithm that uses (O) over tilde (n) space, and with high probability, recover ...

ASSOC COMPUTING MACHINERY2020

An Optimal Space Lower Bound for Approximating MAX-CUT

Mikhail Kapralov

We consider the problem of estimating the value of MAX-CUT in a graph in the streaming model of computation. At one extreme, there is a trivial 2-approximation for this problem that uses only O(log n) space, namely, count the number of edges and output hal ...

ASSOC COMPUTING MACHINERY2019

Indiscreet logarithms in finite fields of small characteristic

Robert Granger, Thorsten Kleinjung, Jens Markus Zumbrägel

Recently, several striking advances have taken place regarding the discrete logarithm problem (DLP) in finite fields of small characteristic, despite progress having remained essentially static for nearly thirty years, with the best known algorithms being ...

2018

Tight Bounds for Asynchronous Renaming

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

This article presents the first tight bounds on the time complexity of shared-memory renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct identifiers from a small namespace. We first prove an individual ...

Association for Computing Machinery2014

On the Function Field Sieve and the Impact of Higher Splitting Probabilities: Application to Discrete Logarithms in $\mathbb{F}_{2^{1971}}$ and $\mathbb{F}_{2^{3164}}$

Robert Granger, Jens Markus Zumbrägel

In this paper we propose a binary field variant of the Joux-Lercier medium-sized Function Field Sieve, which results not only in complexities as low as

L_{q^n}(1/3,(4/9)1/3)

for computing arbitrary logarithms, but also in an heuristic polynomial time alg ...

Springer Berlin Heidelberg2013

On the Construction of Polar Codes

Emre Telatar, Seyed Hamed Hassani, Ramtin Pedarsani

We consider the problem of efficiently constructing polar codes over binary memoryless symmetric (BMS) channels. The complexity of designing polar codes via an exact evaluation of the polarized channels to find which ones are "good" appears to be exponenti ...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2011

Fast Randomized Test-and-Set and Renaming

Rachid Guerraoui, Seth Gilbert, Dan Alistarh, Hagit Albo Attiya, Andrei Giurgiu

Most people believe that renaming is easy: simply choose a name \emph{at random}; if more than one process selects the same name, then try again. We highlight the issues that occur when trying to implement such a scheme and shed new light on the read-write ...

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2010

Estimates for Discrete Logarithm Computations in Finite Fields of Small Characteristic

Robert Granger

We give estimates for the running-time of the function field sieve (FFS) to compute discrete logarithms in

\mathbb{F}_{p^n}^{\times}

for small

p

. Specifically, we obtain sharp probability estimates that allow us to select optimal parameters in cases of ...

Springer Berlin Heidelberg2003

The magic words are squeamish ossifrage [RSA public key cryptography]

Arjen Lenstra, Pénélope Leyland

We describe the computation which resulted in the title of this paper. Furthermore, we give an analysis of the data collected during this computation. From this data, we derive the important observation that in the final stages, the progress of the double ...

1995

L-notation

Graph Chatbot

Chat with Graph Search

Fast and Space Efficient Spectral Sparsification in Dynamic Streams

An Optimal Space Lower Bound for Approximating MAX-CUT

Indiscreet logarithms in finite fields of small characteristic

Tight Bounds for Asynchronous Renaming

On the Function Field Sieve and the Impact of Higher Splitting Probabilities: Application to Discrete Logarithms in $\mathbb{F}_{2^{1971}}$ and $\mathbb{F}_{2^{3164}}$

On the Construction of Polar Codes

Fast Randomized Test-and-Set and Renaming

Estimates for Discrete Logarithm Computations in Finite Fields of Small Characteristic

The magic words are squeamish ossifrage [RSA public key cryptography]

The magic words are squeamish ossifrage [RSA public key cryptography]

Tight Bounds for Asynchronous Renaming

On the Construction of Polar Codes

Estimates for Discrete Logarithm Computations in Finite Fields of Small Characteristic

An Optimal Space Lower Bound for Approximating MAX-CUT

Fast and Space Efficient Spectral Sparsification in Dynamic Streams

Indiscreet logarithms in finite fields of small characteristic

Fast Randomized Test-and-Set and Renaming

On the Function Field Sieve and the Impact of Higher Splitting Probabilities: Application to Discrete Logarithms in $\mathbb{F}_{2^{1971}}$ and $\mathbb{F}_{2^{3164}}$