اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدLocks and keys: How fast can you open several locks with too many keys?
50
0
0.0
(
0
)
تأليف
Olivier Marchal
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
This short note is the result of a French Hippocampe internship that aims at introducing the world of research to young undergraduate French students. The problem studied is the following: imagine yourself locked in a cage barred with $n$ different locks. You are given a keyring with $N geq n$ keys containing the $n$ keys that open the locks. In average, how many trials are required to open all locks and get out? The article studies $3$ different strategies and compare them. Implementation of the strategies are also proposed as illustrations of the theoretical results.
قيم البحث
اقرأ أيضاً
Based on quantum encryption, we present a new idea for quantum public-key cryptography (QPKC) and construct a whole theoretical framework of a QPKC system. We show that the quantum-mechanical nature renders it feasible and reasonable to use symmetric
keys in such a scheme, which is quite different from that in conventional public-key cryptography. The security of our scheme is analyzed and some features are discussed. Furthermore, the state-estimation attack to a prior QPKC scheme is demonstrated.
This paper introduces a structured memory which can be easily integrated into a neural network. The memory is very large by design and significantly increases the capacity of the architecture, by up to a billion parameters with a negligible computati
onal overhead. Its design and access pattern is based on product keys, which enable fast and exact nearest neighbor search. The ability to increase the number of parameters while keeping the same computational budget lets the overall system strike a better trade-off between prediction accuracy and computation efficiency both at training and test time. This memory layer allows us to tackle very large scale language modeling tasks. In our experiments we consider a dataset with up to 30 billion words, and we plug our memory layer in a state-of-the-art transformer-based architecture. In particular, we found that a memory augmented model with only 12 layers outperforms a baseline transformer model with 24 layers, while being twice faster at inference time. We release our code for reproducibility purposes.
A challenge for programming language research is to design and implement multi-threaded low-level languages providing static guarantees for memory safety and freedom from data races. Towards this goal, we present a concurrent language employing safe
region-based memory management and hierarchical locking of regions. Both regions and locks are treated uniformly, and the language supports ownership transfer, early deallocation of regions and early release of locks in a safe manner.
Any secured system can be modeled as a capability-based access control system in which each user is given a set of secret keys of the resources he is granted access to. In some large systems with resource-constrained devices, such as sensor networks
and RFID systems, the design is sensitive to memory or key storage cost. With a goal to minimize the maximum users key storage, key compression based on key linking, that is, deriving one key from another without compromising security, is studied. A lower bound on key storage needed for a general access structure with key derivation is derived. This bound demonstrates the theoretic limit of any systems which do not trade off security and can be treated as a negative result to provide ground for designs with security tradeoff. A concrete, provably secure key linking scheme based on pseudorandom functions is given. Using the key linking framework, a number of key pre-distribution schemes in the literature are analyzed.
In order to understand the relative expressive power of larger concurrent programming languages, we analyze translations of small process calculi which model the communication and synchronization of concurrent processes. The source language SYNCSIMPL
E is a minimalistic model for message passing concurrency while the target language LOCKSIMPLE is a minimalistic model for shared memory concurrency. The former is a calculus with synchronous communication of processes, while the latter has synchronizing mutable locations - called locks - that behave similarly to binary semaphores. The criteria for correctness of translations is that they preserve and reflect may-termination and must-termination of the processes. We show that there is no correct compositional translation from SYNCSIMPLE to LOCKSIMPLE that uses one or two locks, independent from the initialisation of the locks. We also show that there is a correct translation that uses three locks. Also variants of the locks are taken into account with different blocking behavior.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
