Exponential time hypothesis

Formal sciences
Theoretical computer science
Theory of computation
Computational complexity th...

About
Privacy
Disclaimer

Graph Chatbot

Related publications (28)

Page 2 of 2

DESIA: A General Framework for Designing Interlocking Assemblies

Mark Pauly, Ziqi Wang, Peng Song

Interlocking assemblies have a long history in the design of puzzles, furniture, architecture, and other complex geometric structures. The key defining property of interlocking assemblies is that all component parts are immobilized by their geometric arran ...

2018

DESIA: A General Framework for Designing Interlocking Assemblies

Mark Pauly, Ziqi Wang, Peng Song

ASSOC COMPUTING MACHINERY2018

Indiscreet logarithms in finite fields of small characteristic

Thorsten Kleinjung, Robert Granger, 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

SAT-Based Area Recovery in Structural Technology Mapping

Bruno Schmitt Antunes

This paper proposes a fast SAT-based algorithm for recovering area applicable to an already technology mapped circuit. The algorithm considers a sequence of relatively small overlapping regions, called windows, in a mapped network and tries to improve the ...

ASSOC COMPUTING MACHINERY2018

Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits

Ola Nils Anders Svensson, Abbas Bazzi

Initially developed for the min-knapsack problem, the knapsack cover inequalities are used in the current best relaxations for numerous combinatorial optimization problems of covering type. In spite of their widespread use, these inequalities yield linear ...

UNIV CHICAGO, DEPT COMPUTER SCIENCE2018

When Stuck, Flip a Coin : New Algorithms for Large-Scale Tasks

Slobodan Mitrovic

Many modern services need to routinely perform tasks on a large scale. This prompts us to consider the following question: How can we design efficient algorithms for large-scale computation? In this thesis, we focus on devising a general strategy to addr ...

EPFL2018

Low-rank tensor methods for large Markov chains and forward feature selection methods

Francisco Santos Paredes Quartin de Macedo

In the first part of this thesis, we present and compare several approaches for the determination of the steady-state of large-scale Markov chains with an underlying low-rank tensor structure. Such structure is, in our context of interest, associated with ...

EPFL2018

Exponential extinction time of the contact process on finite graphs

Thomas Mountford, Jean-Christophe Mourrat, Daniel Rodrigues Valesin

We study the extinction time tau of the contact process started with full occupancy on finite trees of bounded degree. We show that, if the infection rate is larger than the critical rate for the contact process on Z, then, uniformly over all trees of degr ...

Elsevier Science Bv2016