Concept

Asymptotic computational complexity

Related publications (64)

Extended Navigability of Small World Networks: Exact Results and New Insights

Paolo De Los Rios, Cécile Caretta Cartozo

Navigability of networks, that is, the ability to find any given destination vertex starting from any other vertex, is crucial to their usefulness. In 2000 Kleinberg showed that optimal navigability could be achieved in small world networks provided that a ...

American Physical Society2009

Finding Hamiltonian circuits in quasi-adjoint graphs

Dominique de Werra, Benjamin Leroy-Beaulieu

This paper is motivated by a method used for DNA sequencing by hybridization presented in [Jacek Blazewicz, Marta Kasprzak, Computational complexity of isothernnic DNA sequencing by hybridization, Discrete Appl. Math. 154 (5) (2006) 718-7291. This paper pr ...

2008

An asymptotic result for Brownian polymers

Thomas Mountford

We consider a model of the shape of a growing polymer introduced by Durrett and Rogers (Probab. Theory Related Fields 92 (1992) 337-349). We prove their conjecture about the asymptotic behavior of the underlying continuous process X-t (corresponding to the ...

2008

Some Issues on the p-Laplace Equation in Cylindrical Domains

We investigate the asymptotic behavior of the solution to equations of the p-Laplacian type in cylindrical domains becoming unbounded and address some issues regarding the solution in unbounded domains. ...

2008

A profiling framework for high level design space exploration for memory and system architectures

In 1971, the first microprocessor produced in mass production had 2300 transistor and was able to compute 60'000 operations per second at 740 kHz. Nowadays, even a common gaming console uses a central unit including 243 millions of transistors running at 4 ...

EPFL2007

Capacity upper bounds for the deletion channel

Suhas Diggavi, Henry Pfister

We present two upper bounds on the capacity of the i.i.d. binary deletion channel, where each bit is independently deleted with a fixed probability d. The first can be numerically evaluated for any fixed d. The second provides an asymptotic upper bound as ...

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

Classes of stochastically switched (blinking) systems

Martin Hasler, Igor Belykh

It is investigated to what extent the trajectories of a stochastically switched (blinking) system follow the corresponding trajectories of the averaged system. Four cases have to be distinguished, depending on whether or not the averaged system has a uniqu ...

2007

Reverse Search for Parametric Linear Programming

Colin Neil Jones

This paper introduces a new enumeration technique for (multi)parametric linear programs (pLPs) based on the reverse-search paradigm. We prove that the proposed algorithm has a computational complexity that is linear in the size of the output (number of so- ...

IEEE2006

Computational Hardness and Explicit Constructions of Error Correcting Codes

Mohammad Amin Shokrollahi, Mahdi Cheraghchi Bashi Astaneh

We outline a procedure for using pseudorandom generators to construct binary codes with good properties, assuming the existence of sufficiently hard functions. Specifically, we give a polynomial time algorithm, which for every integers

n

and

k

, constru ...

2006

Toward Online Probabilistic Path Replanning

Roland Siegwart, Björn Jensen, Roland Philippsen

In this talk we present work on sensor-based motion planning in initially unknown dynamic environments. Motion detection and probabilistic motion modeling are combined with a smooth navigation function to perform on-line path planning and replanning in clu ...

2006

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.

Computational Hardness and Explicit Constructions of Error Correcting Codes

Mohammad Amin Shokrollahi, Mahdi Cheraghchi Bashi Astaneh

n

and

k

, constru ...

2006