Game complexity

Combinatorial game theory measures game complexity in several ways: #State-space complexity (the number of legal game positions from the initial position), #Game tree size (total number of possible games), #Decision complexity (number of leaf nodes in the smallest decision tree for initial position), #Game-tree complexity (number of leaf nodes in the smallest full-width decision tree for initial position), #Computational complexity (asymptotic difficulty of a game as it grows arbitrarily large). These measures involve understanding game positions, possible outcomes, and computation required for various game scenarios. Measures of game complexity State-space complexity The state-space complexity of a game is the number of legal game positions reachable from the initial position of the game. When this is too hard to calculate, an upper bound can often be computed by also counting (some) illegal positions, meaning positions that can ne

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (12)

Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés (11)

Concepts associés

Chargement

Cours associés (7)

Cours associés

Chargement

Séances de cours associées (9)

Séances de cours associées

Chargement

Reducing Memory Requirements for Combinatorial Attacks on NTRU via Multiple Birthdays

In this paper we view the possibilities to lance a multiple (iterative) birthday attack on NTRU. Recently Wagner's algorithm for the generalized birthday problem [9] allowed to speed-up several combinatorial attacks. However, in the case of NTRU we can not hope to to apply Wagner's algorithm directly, as the search space does not behave nicely. In this paper we show that we can nevertheless draw profit from a multiple birthday approach. Our approach allows us to attack ees251ep6 parameter set on a computer with only 2(52) Bits of memory and about 2(9) times faster as with Odlyzko's combinatorial attack - this is an improvement factor about 2(43) in space complexity. We thus contradict the common believe, that in comparison to computational requirements, the "storage requirement is by far the larger obstacle" [3] to attack NTRU by combinatorial attacks. Further, our attack is about 2(7) times faster than the space-reduced variant from [3] employing the same amount of memory.

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

Chargement

A multiple birthday attack on NTRU

In this paper we view the possibilities to lance a multiple (iterative) birthday attack on NTRU. Recently Wagner's algorithm for the generalized birthday problem (Wagner, 2002) allowed to speed-up several combinatorial attacks. However, in the case of NTRU we can not hope to to apply Wagner's algorithm directly, as the search space does not behave nicely. In this paper we show that we can nevertheless draw profit from a multiple birthday approach. Our approach allows us to attack ees251ep6 parameter set on a computer with only 252 Bits of memory and about 29 times faster as with Odlyzko's combinatorial attack - this is an improvement factor about 243 in space complexity. We thus contradict the common believe, that in comparison to computational requirements, the "storage requirement is by far the larger obstacle" (Howgrave-Graham, 2007) to attack NTRU by combinatorial attacks. Further, our attack is about 27 times faster than the space-reduced variant from (Howgrave-Graham, 2007) employing the same amount of memory.

Insticc-Inst Syst Technologies Information Control & Communication, Avenida D Manuel L, 27A 2 Esquerdo, Setubal, 2910-595, Portugal2008

Chargement

A Non-Euclidean Gradient Descent Framework for Non-Convex Matrix Factorization

Volkan Cevher, Ya-Ping Hsieh, Yu-Chun Kao, Rabeeh Karimi Mahabadi, Anastasios Kyrillidis

We study convex optimization problems that feature low-rank matrix solutions. In such scenarios, non-convex methods offer significant advantages over convex methods due to their lower space complexity as well as faster convergence speed. Moreover, many of these methods feature rigorous approximation guarantees. Non-convex algorithms are simple to analyze and implement as they perform Euclidean gradient descent on matrix factors. In contrast, this paper derives non-Euclidean optimization frame- work in the non-convex setting that takes nonlinear gradient steps on the factors. We prove convergence rates to the global minimum under appropriate assumptions. We provide numerical evidence with Fourier Ptychography and FastText applications using real data that shows our approach can significantly enhance solution quality

2018

Chargement

CS-430: Intelligent agents

Software agents are widely used to control physical, economic and financial processes. The course presents practical methods for implementing software agents and multi-agent systems, supported by programming exercises, and the theoretical underpinnings including computational game theory.

MGT-454: Principles of microeconomics

The course allows students to get familiarized with the basic tools and concepts of modern microeconomic analysis. Based on graphical reasoning and analytical calculus, it constantly links to real economic issues.

COM-401: Cryptography and security

This course introduces the basics of cryptography. We review several types of cryptographic primitives, when it is safe to use them and how to select the appropriate security parameters. We detail how they work and sketch how they can be implemented.

Théorie des jeux

La théorie des jeux est un domaine des mathématiques qui propose une description formelle d'interactions stratégiques entre agents (appelés « joueurs »). Les fondements mathématiques de la théorie m

Programme d'échecs

vignette|Jeu d'échecs électronique des années 1990 avec écran LCD. Un programme d'échecs est un programme informatique conçu pour jouer au jeu d'échecs. Historique Débuts et développ

Théorie des jeux combinatoires

La théorie des jeux combinatoires est une théorie mathématique qui étudie les jeux à deux joueurs comportant un concept de position, et où les joueurs jouent à tour de rôle un coup d'une façon défi