---
_id: '14693'
abstract:
- lang: eng
text: "Lucas sequences are constant-recursive integer sequences with a long history
of applications in cryptography, both in the design of cryptographic schemes and
cryptanalysis. In this work, we study the sequential hardness of computing Lucas
sequences over an RSA modulus.\r\nFirst, we show that modular Lucas sequences
are at least as sequentially hard as the classical delay function given by iterated
modular squaring proposed by Rivest, Shamir, and Wagner (MIT Tech. Rep. 1996)
in the context of time-lock puzzles. Moreover, there is no obvious reduction in
the other direction, which suggests that the assumption of sequential hardness
of modular Lucas sequences is strictly weaker than that of iterated modular squaring.
In other words, the sequential hardness of modular Lucas sequences might hold
even in the case of an algorithmic improvement violating the sequential hardness
of iterated modular squaring.\r\nSecond, we demonstrate the feasibility of constructing
practically-efficient verifiable delay functions based on the sequential hardness
of modular Lucas sequences. Our construction builds on the work of Pietrzak (ITCS
2019) by leveraging the intrinsic connection between the problem of computing
modular Lucas sequences and exponentiation in an appropriate extension field."
acknowledgement: "Home Theory of Cryptography Conference paper\r\n(Verifiable) Delay
Functions from Lucas Sequences\r\nDownload book PDF\r\nDownload book EPUB\r\nSimilar
content being viewed by others\r\n\r\nSlider with three content items shown per
slide. Use the Previous and Next buttons to navigate the slides or the slide controller
buttons at the end to navigate through each slide.\r\nPrevious slide\r\nGeneric-Group
Delay Functions Require Hidden-Order Groups\r\nChapter© 2020\r\n\r\nShifted powers
in Lucas–Lehmer sequences\r\nArticle30 January 2019\r\n\r\nA New Class of Trapdoor
Verifiable Delay Functions\r\nChapter© 2023\r\n\r\nWeak Pseudoprimality Associated
with the Generalized Lucas Sequences\r\nChapter© 2022\r\n\r\nOn the Security of
Time-Lock Puzzles and Timed Commitments\r\nChapter© 2020\r\n\r\nGeneration of full
cycles by a composition of NLFSRs\r\nArticle08 March 2014\r\n\r\nCryptographically
Strong de Bruijn Sequences with Large Periods\r\nChapter© 2013\r\n\r\nOpen Problems
on With-Carry Sequence Generators\r\nChapter© 2014\r\n\r\nGenerically Speeding-Up
Repeated Squaring Is Equivalent to Factoring: Sharp Thresholds for All Generic-Ring
Delay Functions\r\nChapter© 2020\r\n\r\nNext slide\r\nGo to slide 1\r\nGo to slide
2\r\nGo to slide 3\r\n(Verifiable) Delay Functions from Lucas Sequences\r\nCharlotte
Hoffmann, Pavel Hubáček, Chethan Kamath & Tomáš Krňák \r\nConference paper\r\nFirst
Online: 27 November 2023\r\n83 Accesses\r\n\r\nPart of the Lecture Notes in Computer
Science book series (LNCS,volume 14372)\r\n\r\nAbstract\r\nLucas sequences are constant-recursive
integer sequences with a long history of applications in cryptography, both in the
design of cryptographic schemes and cryptanalysis. In this work, we study the sequential
hardness of computing Lucas sequences over an RSA modulus.\r\n\r\nFirst, we show
that modular Lucas sequences are at least as sequentially hard as the classical
delay function given by iterated modular squaring proposed by Rivest, Shamir, and
Wagner (MIT Tech. Rep. 1996) in the context of time-lock puzzles. Moreover, there
is no obvious reduction in the other direction, which suggests that the assumption
of sequential hardness of modular Lucas sequences is strictly weaker than that of
iterated modular squaring. In other words, the sequential hardness of modular Lucas
sequences might hold even in the case of an algorithmic improvement violating the
sequential hardness of iterated modular squaring.\r\n\r\nSecond, we demonstrate
the feasibility of constructing practically-efficient verifiable delay functions
based on the sequential hardness of modular Lucas sequences. Our construction builds
on the work of Pietrzak (ITCS 2019) by leveraging the intrinsic connection between
the problem of computing modular Lucas sequences and exponentiation in an appropriate
extension field.\r\n\r\nKeywords\r\nDelay functions\r\nVerifiable delay functions\r\nLucas
sequences\r\nDownload conference paper PDF\r\n\r\n1 Introduction\r\nA verifiable
delay function (VDF) \r\n is a function that satisfies two properties. First, it
is a delay function, which means it must take a prescribed (wall) time T to compute
f, irrespective of the amount of parallelism available. Second, it should be possible
for anyone to quickly verify – say, given a short proof \r\n – the value of the
function (even without resorting to parallelism), where by quickly we mean that
the verification time should be independent of or significantly smaller than T (e.g.,
logarithmic in T). If we drop either of the two requirements, then the primitive
turns out trivial to construct. For instance, for an appropriately chosen hash function
h, the delay function \r\n defined by T-times iterated hashing of the input is a
natural heuristic for an inherently sequential task which, however, seems hard to
verify more efficiently than by recomputing. On the other hand, the identity function
\r\n is trivial to verify but also easily computable. Designing a simple function
satisfying the two properties simultaneously proved to be a nontrivial task.\r\n\r\nThe
notion of VDFs was introduced in [31] and later formalised in [9]. In principle,
since the task of constructing a VDF reduces to the task of incrementally-verifiable
computation [9, 53], constructions of VDFs could leverage succinct non-interactive
arguments of knowledge (SNARKs): take any sequentially-hard function f (for instance,
iterated hashing) as the delay function and then use the SNARK on top of it as the
mechanism for verifying the computation of the delay function. However, as discussed
in [9], the resulting construction is not quite practical since we would rely on
a general-purpose machinery of SNARKs with significant overhead.\r\n\r\nEfficient
VDFs via Algebraic Delay Functions. VDFs have recently found interesting applications
in design of blockchains [17], randomness beacons [43, 51], proofs of data replication
[9], or short-lived zero-knowledge proofs and signatures [3]. Since efficiency is
an important factor there, this has resulted in a flurry of constructions of VDFs
that are tailored with application and practicality in mind. They rely on more algebraic,
structured delay functions that often involve iterating an atomic operation so that
one can resort to custom proof systems to achieve verifiability. These constructions
involve a range of algebraic settings like the RSA or class groups [5, 8, 25, 42,
55], permutation polynomials over finite fields [9], isogenies of elliptic curves
[21, 52] and, very recently, lattices [15, 28]. The constructions in [42, 55] are
arguably the most practical and the mechanism that underlies their delay function
is the same: carry out iterated squaring in groups of unknown order, like RSA groups
[47] or class groups [12]. What distinguishes these two proposals is the way verification
is carried out, i.e., how the underlying “proof of exponentiation” works: while
Pietrzak [42] resorts to an LFKN-style recursive proof system [35], Wesolowski [55]
uses a clever linear decomposition of the exponent.\r\n\r\nIterated Modular Squaring
and Sequentiality. The delay function that underlies the VDFs in [5, 25, 42, 55]
is the same, and its security relies on the conjectured sequential hardness of iterated
squaring in a group of unknown order (suggested in the context of time-lock puzzles
by Rivest, Shamir, and Wagner [48]). Given that the practically efficient VDFs all
rely on the above single delay function, an immediate open problem is to identify
additional sources of sequential hardness that are structured enough to support
practically efficient verifiability.\r\n\r\n1.1 Our Approach to (Verifiable) Delay
Functions\r\nIn this work, we study an alternative source of sequential hardness
in the algebraic setting and use it to construct efficient verifiable delay functions.
The sequentiality of our delay function relies on an atomic operation that is related
to the computation of so-called Lucas sequences [29, 34, 57], explained next.\r\n\r\nLucas
Sequences. A Lucas sequence is a constant-recursive integer sequence that satisfies
the recurrence relation\r\n\r\nfor integers P and Q.Footnote1 Specifically, the
Lucas sequences of integers \r\n and \r\n of the first and second type (respectively)
are defined recursively as\r\n\r\nwith \r\n, and\r\n\r\nwith \r\n.\r\n\r\nThese
sequences can be alternatively defined by the characteristic polynomial \r\n. Specifically,
given the discriminant \r\n of the characteristic polynomial, one can alternatively
compute the above sequences by performing operations in the extension field\r\n\r\nusing
the identities\r\n\r\nwhere \r\n and its conjugate \r\n are roots of the characteristic
polynomial. Since conjugation and exponentiation commute in the extension field
(i.e., \r\n), computing the i-th terms of the two Lucas sequences over integers
reduces to computing \r\n in the extension field, and vice versa.\r\n\r\nThe intrinsic
connection between computing the terms in the Lucas sequences and that of exponentiation
in the extension has been leveraged to provide alternative instantiations of public-key
encryption schemes like RSA and ElGamal in terms of Lucas sequences [7, 30]. However,
as we explain later, the corresponding underlying computational hardness assumptions
are not necessarily equivalent.\r\n\r\nOverview of Our Delay Function. The delay
function in [5, 25, 42, 55] is defined as the iterated squaring base x in a (safe)
RSA groupFootnote2 modulo N:\r\n\r\nOur delay function is its analogue in the setting
of Lucas sequences:\r\n\r\nAs mentioned above, computing \r\n can be carried out
equivalently in the extension field \r\n using the known relationship to roots of
the characteristic polynomial of the Lucas sequence. Thus, the delay function can
be alternatively defined as\r\n\r\nNote that the atomic operation of our delay function
is “doubling” the index of an element of the Lucas sequence modulo N (i.e., \r\n)
or, equivalently, squaring in the extension field \r\n (as opposed to squaring in
\r\n). Using the representation of \r\n as \r\n, squaring in \r\n can be expressed
as a combination of squaring, multiplication and addition modulo N, since\r\n\r\n(1)\r\nSince
\r\n is a group of unknown order (provided the factorization of N is kept secret),
iterated squaring remains hard here. In fact, we show in Sect. 3.2 that iterated
squaring in \r\n is at least as hard as iterated squaring for RSA moduli N. Moreover,
we conjecture in Conjecture 1 that it is, in fact, strictly harder (also see discussion
below on advantages of our approach).\r\n\r\nVerifying Modular Lucas Sequence. To
obtain a VDF, we need to show how to efficiently verify our delay function. To this
end, we show how to adapt the interactive proof of exponentiation from [42] to our
setting, which then – via the Fiat-Shamir Transform [22] – yields the non-interactive
verification algorithm.Footnote3 Thus, our main result is stated informally below.\r\n\r\nTheorem
1\r\n(Informally stated, see Theorem 2). Assuming sequential hardness of modular
Lucas sequence, there exists statistically-sound VDF in the random-oracle model.\r\n\r\nHowever,
the modification of Pietrzak’s protocol is not trivial and we have to overcome several
hurdles that we face in this task, which we elaborate on in Sect. 1.2. We conclude
this section with discussions about our results.\r\n\r\nAdvantage of Our Approach.
Our main advantage is the reliance on a potentially weaker (sequential) hardness
assumption while maintaining efficiency: we show in Sect. 3.2 that modular Lucas
sequences are at least as sequentially-hard as the classical delay function given
by iterated modular squaring [48]. Despite the linear recursive structure of Lucas
sequences, there is no obvious reduction in the other direction, which suggests
that the assumption of sequential hardness of modular Lucas sequences is strictly
weaker than that of iterated modular squaring (Conjecture 1). In other words, the
sequential hardness of modular Lucas sequences might hold even in the case of an
algorithmic improvement violating the sequential hardness of iterated modular squaring.
Even though both assumptions need the group order to be hidden, we believe that
there is need for a nuanced analysis of sequential hardness assumptions in hidden
order groups, especially because all current delay functions that provide sufficient
structure for applications are based on iterated modular squaring. If the iterated
modular squaring assumption is broken, our delay function is currently the only
practical alternative in the RSA group.\r\n\r\nDelay Functions in Idealised Models.
Recent works studied the relationship of group-theoretic (verifiable) delay functions
to the hardness of factoring in idealised models such as the algebraic group model
and the generic ring model [27, 50]. In the generic ring model, Rotem and Segev
[50] showed the equivalence of straight-line delay functions in the RSA setting
and factoring. Our construction gives rise to a straight-line delay function and,
by their result, its sequentiality is equivalent to factoring for generic algorithms.
However, their result holds only in the generic ring model and leaves the relationship
between the two assumptions unresolved in the standard model.\r\n\r\nCompare this
with the status of the RSA assumption and factoring. On one hand, we know that in
the generic ring model, RSA and factoring are equivalent [2]. Yet, it is possible
to rule out certain classes of reductions from factoring to RSA in the standard
model [11]. Most importantly, despite the equivalence in the generic ring model,
there is currently no reduction from factoring to RSA in the standard model and
it remains one of the major open problems in number theory related to cryptography
since the introduction of the RSA assumption.\r\n\r\nIn summary, speeding up iterated
squaring by a non-generic algorithm could be possible (necessarily exploiting the
representations of ring elements modulo N), while such an algorithm may not lead
to a speed-up in the computation of modular Lucas sequences despite the result of
Rotem and Segev [50].\r\n\r\n1.2 Technical Overview\r\nPietrzak’s VDF. Let \r\n
be an RSA modulus where p and q are safe primes and let x be a random element from
\r\n. At its core, Pietrzak’s VDF relies on the interactive protocol for the statement\r\n\r\n“(N,
x, y, T) satisfies \r\n”.\r\n\r\nThe protocol is recursive and, in a round-by-round
fashion, reduces the claim to a smaller statement by halving the time parameter.
To be precise, in each round, the (honest) prover sends the “midpoint” \r\n of the
current statement to the verifier and they together reduce the statement to\r\n\r\n“\r\n
satisfies \r\n”,\r\n\r\nwhere \r\n and \r\n for a random challenge r. This is continued
till \r\n is obtained at which point the verifier simply checks whether \r\n using
a single modular squaring.\r\n\r\nSince the challenges r are public, the protocol
can be compiled into a non-interactive one using the Fiat-Shamir transform [22]
and this yields a means to verify the delay function\r\n\r\nIt is worth pointing
out that the choice of safe primes is crucial for proving soundness: in case the
group has easy-to-find elements of small order then it becomes easy to break soundness
(see, e.g., [10]).\r\n\r\nAdapting Pietrzak’s Protocol to Lucas Sequences. For a
modulus \r\n and integers \r\n, recall that our delay function is defined as\r\n\r\nor
equivalently\r\n\r\nfor the discriminant \r\n of the characteristic polynomial \r\n.
Towards building a verification algorithm for this delay function, the natural first
step is to design an interactive protocol for the statement\r\n\r\n“(N, P, Q, y,
T) satisfies \r\n.”\r\n\r\nIt turns out that the interactive protocol from [42]
can be adapted for this purpose. However, we encounter two technicalities in this
process.\r\n\r\nDealing with elements of small order. The main problem that we face
while designing our protocol is avoiding elements of small order. In the case of
[42], this was accomplished by moving to the setting of signed quadratic residues
[26] in which the sub-groups are all of large order. It is not clear whether a corresponding
object exists for our algebraic setting. However, in an earlier draft of Pietrzak’s
protocol [41], this problem was dealt with in a different manner: the prover sends
a square root of \r\n, from which the original \r\n can be recovered easily (by
squaring it) with a guarantee that the result lies in a group of quadratic residues
\r\n. Notice that the prover knows the square root of \r\n, because it is just a
previous term in the sequence he computed.\r\n\r\nIn our setting, we cannot simply
ask for the square root of the midpoint as the subgroup of \r\n we effectively work
in has a different structure. Nevertheless, we can use a similar approach: for an
appropriately chosen small a, we provide an a-th root of \r\n (instead of \r\n itself)
to the prover in the beginning of the protocol. The prover then computes the whole
sequence for \r\n. In the end, he has the a-th root of every term of the original
sequence and he can recover any element of the original sequence by raising to the
a-th power.\r\n\r\nSampling strong modulus. The second technicality is related to
the first one. In order to ensure that we can use the above trick, we require a
modulus where the small subgroups are reasonably small not only in the group \r\n
but also in the extension \r\n. Thus the traditional sampling algorithms that are
used to sample strong primes (e.g., [46]) are not sufficient for our purposes. However,
sampling strong primes that suit our criteria can still be carried out efficiently
as we show in the full version.\r\n\r\nComparing Our Technique with [8, 25]. The
VDFs in [8, 25] are also inspired by [42] and, hence, faced the same problem of
low-order elements. In [8], this is dealt with by amplifying the soundness at the
cost of parallel repetition and hence larger proofs and extra computation. In [25],
the number of repetitions of [8] is reduced significantly by introducing the following
technique: The exponent of the initial instance is reduced by some parameter \r\n
and at the end of an interactive phase, the verifier performs final exponentiation
with \r\n, thereby weeding out potential false low-order elements in the claim.
This technique differs from the approach taken in our work in the following ways:
The technique from [25] works in arbitrary groups but it requires the parameter
\r\n to be large and of a specific form. In particular, the VDF becomes more efficient
when \r\n is larger than \r\n. In our protocol, we work in RSA groups whose modulus
is the product of primes that satisfy certain conditions depending on a. This enables
us to choose a parameter a that is smaller than a statistical security parameter
and thereby makes the final exponentiation performed by the verifier much more efficient.
Further, a can be any natural number, while \r\n must be set as powers of all small
prime numbers up a certain bound in [25].\r\n\r\n1.3 More Related Work\r\nTimed
Primitives. The notion of VDFs was introduced in [31] and later formalised in [9].
VDFs are closely related to the notions of time-lock puzzles [48] and proofs of
sequential work [36]. Roughly speaking, a time-lock puzzle is a delay function that
additionally allows efficient sampling of the output via a trapdoor. A proof of
sequential work, on the other hand, is a delay “multi-function”, in the sense that
the output is not necessarily unique. Constructions of time-lock puzzles are rare
[6, 38, 48], and there are known limitations: e.g., that it cannot exist in the
random-oracle model [36]. However, we know how to construct proofs of sequential
work in the random-oracle model [1, 16, 19, 36].\r\n\r\nSince VDFs have found several
applications, e.g., in the design of resource-efficient blockchains [17], randomness
beacons [43, 51] and proof of data replication [9], there have been several constructions.
Among them, the most notable are the iterated-squaring based construction from [8,
25, 42, 55], the permutation-polynomial based construction from [9], the isogenies-based
construction from [13, 21, 52] and the construction from lattice problems [15, 28].
The constructions in [42, 55] are quite practical (see the survey [10]) and the
VDF deployed in the cryptocurrency Chia is basically their construction adapted
to the algebraic setting of class groups [17]. This is arguably the closest work
to ours. On the other hand, the constructions from [21, 52], which work in the algebraic
setting of isogenies of elliptic curves where no analogue of square and multiply
is known, simply rely on “exponentiation”. Although, these constructions provide
a certain form of quantum resistance, they are presently far from efficient. Freitag
et al. [23] constructed VDFs from any sequentially hard function and polynomial
hardness of learning with errors, the first from standard assumptions. The works
of Cini, Lai, and Malavolta [15, 28] constructed the first VDF from lattice-based
assumptions and conjectured it to be post-quantum secure.\r\n\r\nSeveral variants
of VDFs have also been proposed. A VDF is said to be unique if the proof that is
used for verification is unique [42]. Recently, Choudhuri et al. [5] constructed
unique VDFs from the sequential hardness of iterated squaring in any RSA group and
polynomial hardness of LWE. A VDF is tight [18] if the gap between simply computing
the function and computing it with a proof is small. Yet another extension is a
continuous VDF [20]. The feasibility of time-lock puzzles and proofs of sequential
works were recently extended to VDFs. It was shown [50] that the latter requirement,
i.e., working in a group of unknown order, is inherent in a black-box sense. It
was shown in [18, 37] that there are barriers to constructing tight VDFs in the
random-oracle model.\r\n\r\nVDFs also have surprising connection to complexity theory
[14, 20, 33].\r\n\r\nWork Related to Lucas Sequences. Lucas sequences have long
been studied in the context of number theory: see for example [45] or [44] for a
survey of its applications to number theory. Its earliest application to cryptography
can be traced to the \r\n factoring algorithm [56]. Constructive applications were
found later thanks to the parallels with exponentiation. Several encryption and
signature schemes were proposed, most notably the LUC family of encryption and signatures
[30, 39]. It was later shown that some of these schemes can be broken or that the
advantages it claimed were not present [7]. Other applications can be found in [32].\r\n\r\n2
Preliminaries\r\n2.1 Interactive Proof Systems\r\nInteractive Protocols. An interactive
protocol consists of a pair \r\n of interactive Turing machines that are run on
a common input \r\n. The first machine \r\n is the prover and is computationally
unbounded. The second machine \r\n is the verifier and is probabilistic polynomial-time.\r\n\r\nIn
an \r\n-round (i.e., \r\n-message) interactive protocol, in each round \r\n, first
\r\n sends a message \r\n to \r\n and then \r\n sends a message \r\n to \r\n, where
\r\n is a finite alphabet. At the end of the interaction, \r\n runs a (deterministic)
Turing machine on input \r\n. The interactive protocol is public-coin if \r\n is
a uniformly distributed random string in \r\n.\r\n\r\nInteractive Proof Systems.
The notion of an interactive proof for a language L is due to Goldwasser, Micali
and Rackoff [24].\r\n\r\nDefinition 1\r\nFor a function \r\n, an interactive protocol
\r\n is an \r\n-statistically-sound interactive proof system for L if:\r\n\r\nCompleteness:
For every \r\n, if \r\n interacts with \r\n on common input \r\n, then \r\n accepts
with probability 1.\r\n\r\nSoundness: For every \r\n and every (computationally-unbounded)
cheating prover strategy \r\n, the verifier \r\n accepts when interacting with \r\n
with probability less than \r\n, where \r\n is called the soundness error.\r\n\r\n2.2
Verifiable Delay Functions\r\nWe adapt the definition of verifiable delay functions
from [9] but we decouple the verifiability and sequentiality properties for clarity
of exposition of our results. First, we present the definition of a delay function.\r\n\r\nDefinition
2\r\nA delay function \r\n consists of a triple of algorithms with the following
syntax:\r\n\r\n:\r\n\r\nOn input a security parameter \r\n, the algorithm \r\n outputs
public parameters \r\n.\r\n\r\n:\r\n\r\nOn input public parameters \r\n and a time
parameter \r\n, the algorithm \r\n outputs a challenge x.\r\n\r\n:\r\n\r\nOn input
a challenge pair (x, T), the (deterministic) algorithm \r\n outputs the value y
of the delay function in time T.\r\n\r\nThe security property required of a delay
function is sequential hardness as defined below.\r\n\r\nDefinition 3\r\n(Sequentiality).
We say that a delay function \r\n satisfies the sequentiality property, if there
exists an \r\n such that for all \r\n and for every adversary \r\n, where \r\n uses
\r\n processors and runs in time \r\n, there exists a negligible function \r\n such
that\r\n\r\nfigure a\r\nA few remarks about our definition of sequentiality are
in order:\r\n\r\n1.\r\nWe require computing \r\n to be hard in less than T sequential
steps even using any polynomially-bounded amount of parallelism and precomputation.
Note that it is necessary to bound the amount of parallelism, as an adversary could
otherwise break the underlying hardness assumption (e.g. hardness of factorization).
Analogously, T should be polynomial in \r\n as, otherwise, breaking the underlying
hardness assumptions becomes easier than computing \r\n itself for large values
of T.\r\n\r\n2.\r\nAnother issue is what bound on the number of sequential steps
of the adversary should one impose. For example, the delay function based on T repeated
modular squarings can be computed in sequential time \r\n using polynomial parallelism
[4]. Thus, one cannot simply bound the sequential time of the adversary by o(T).
Similarly to [38], we adapt the \r\n bound for \r\n which, in particular, is asymptotically
smaller than \r\n.\r\n\r\n3.\r\nWithout loss of generality, we assume that the size
of \r\n is at least linear in n and the adversary A does not have to get the unary
representation of the security parameter \r\n as its input.\r\n\r\nThe definition
of verifiable delay function extends a delay function with the possibility to compute
publicly-verifiable proofs of correctness of the output value.\r\n\r\nDefinition
4\r\nA delay function \r\n is a verifiable delay function if it is equipped with
two additional algorithms \r\n and \r\n with the following syntax:\r\n\r\n:\r\n\r\nOn
input public parameters and a challenge pair (x, T), the \r\n algorithm outputs
\r\n, where \r\n is a proof that the output y is the output of \r\n.\r\n\r\n:\r\n\r\nOn
input public parameters, a challenge pair (x, T), and an output/proof pair \r\n,
the (deterministic) algorithm \r\n outputs either \r\n or \r\n.\r\n\r\nIn addition
to sequentiality (inherited from the underlying delay function), the \r\n and \r\n
algorithms must together satisfy correctness and (statistical) soundness as defined
below.\r\n\r\nDefinition 5\r\n(Correctness). A verifiable delay function \r\n is
correct if for all \r\n\r\nfigure b\r\nDefinition 6\r\n(Statistical soundness).
A verifiable delay function \r\n is statistically sound if for every (computationally
unbounded) malicious prover \r\n there exists a negligible function \r\n such that
for all \r\n\r\nfigure c\r\n3 Delay Functions from Lucas Sequences\r\nIn this section,
we propose a delay function based on Lucas sequences and prove its sequentiality
assuming that iterated squaring in a group of unknown order is sequential (Sect.
3.1). Further, we conjecture (Sect. 3.2) that our delay function candidate is even
more robust than its predecessor proposed by Rivest, Shamir, and Wagner [48]. Finally,
we turn our delay function candidate into a verifiable delay function (Sect. 4).\r\n\r\n3.1
The Atomic Operation\r\nOur delay function is based on subsequences of Lucas sequences,
whose indexes are powers of two. Below, we use \r\n to denote the set of non-negative
integers.\r\n\r\nDefinition 7\r\nFor integers \r\n, the Lucas sequences \r\n and
\r\n are defined for all \r\n as\r\n\r\nwith \r\n and \r\n, and\r\n\r\nwith \r\n
and \r\n.\r\n\r\nWe define subsequences \r\n, respectively \r\n, of \r\n, respectively
\r\n for all \r\n as\r\n\r\n(2)\r\nAlthough the value of \r\n depends on parameters
(P, Q), we omit (P, Q) from the notation because these parameters will be always
obvious from the context.\r\n\r\nThe underlying atomic operation for our delay function
is\r\n\r\nThere are several ways to compute \r\n in T sequential steps, and we describe
two of them below.\r\n\r\nAn Approach Based on Squaring in a Suitable Extension
Ring. To compute the value \r\n, we can use the extension ring \r\n, where \r\n
is the discriminant of the characteristic polynomial \r\n of the Lucas sequence.
The characteristic polynomial f(z) has a root \r\n, and it is known that, for all
\r\n, it holds that\r\n\r\nThus, by iterated squaring of \r\n, we can compute terms
of our target subsequences. To get a better understanding of squaring in the extension
ring, consider the representation of the root \r\n for some \r\n. Then,\r\n\r\nThen,
the atomic operation of our delay function can be interpreted as \r\n, defined for
all \r\n as\r\n\r\n(3)\r\nAn Approach Based on Known Identities. Many useful identities
for members of modular Lucas sequences are known, such as\r\n\r\n(4)\r\nSetting
\r\n we get\r\n\r\n(5)\r\nThe above identities are not hard to derive (see, e.g.,
Lemma 12.5 in [40]). Indexes are doubled on each of application of the identities
in Eq. (5), and, thus, for \r\n, we define an auxiliary sequence \r\n by \r\n. Using
the identities in Eq. (5), we get recursive equations\r\n\r\n(6)\r\nThen, the atomic
operation of our delay function can be interpreted as \r\n, defined for all \r\n
as\r\n\r\n(7)\r\nAfter a closer inspection, the reader may have an intuition that
an auxiliary sequence \r\n, which introduces a third state variable, is redundant.
This intuition is indeed right. In fact, there is another easily derivable identity\r\n\r\n(8)\r\nwhich
can be found, e.g., as Lemma 12.2 in [40]. On the other hand, Eq. (8) is quite interesting
because it allows us to compute large powers of an element \r\n using two Lucas
sequences. We use this fact in the security reduction in Sect. 3.2. Our construction
of a delay function, denoted \r\n, is given in Fig. 1.\r\n\r\nFig. 1.\r\nfigure
1\r\nOur delay function candidate \r\n based on a modular Lucas sequence.\r\n\r\nFull
size image\r\nOn the Discriminant D. Notice that whenever D is a quadratic residue
modulo N, the value \r\n is an element of \r\n and hence \r\n. By definition, LCS.Gen
generates a parameter D that is a quadratic residue with probability 1/4, so it
might seem that in one fourth of the cases there is another approach to compute
\r\n: find the element \r\n and then perform n sequential squarings in the group
\r\n. However, it is well known that finding square roots of uniform elements in
\r\n is equivalent to factoring the modulus N, so this approach is not feasible.
We can therefore omit any restrictions on the discriminant D in the definition of
our delay function LCS.\r\n\r\n3.2 Reduction from RSW Delay Function\r\nIn order
to prove the sequentiality property (Definition 3) of our candidate \r\n, we rely
on the standard conjecture of the sequentiality of the \r\n time-lock puzzles, implicitly
stated in [48] as the underlying hardness assumption.\r\n\r\nDefinition 8\r\n(\r\n
delay function). The \r\n delay function is defined as follows:\r\n\r\n: Samples
two n-bit primes p and q and outputs \r\n.\r\n\r\n: Outputs an x sampled from the
uniform distribution on \r\n.\r\n\r\n: Outputs \r\n.\r\n\r\nTheorem 2\r\nIf the
\r\n delay function has the sequentiality property, then the \r\n delay function
has the sequentiality property.\r\n\r\nProof\r\nSuppose there exists an adversary
\r\n who contradicts the sequentiality of \r\n, where \r\n is a precomputation algorithm
and \r\n is an online algorithm. We construct an adversary \r\n who contradicts
the sequentiality of \r\n as follows:\r\n\r\nThe algorithm \r\n is defined identically
to the algorithm \r\n.\r\n\r\nOn input \r\n, \r\n picks a P from the uniform distribution
on \r\n, sets\r\n\r\nand it runs \r\n to compute \r\n. The algorithm \r\n computes
\r\n using the identity in Eq. (8).\r\n\r\nNote that the input distribution for
the algorithm \r\n produced by \r\n differs from the one produced by \r\n, because
the \r\n generator samples Q from the uniform distribution on \r\n (instead of \r\n).
However, this is not a problem since the size of \r\n is negligible compared to
the size of \r\n, so the statistical distance between the distribution of D produced
by \r\n and the distribution of D sampled by \r\n is negligible in the security
parameter. Thus, except for a negligible multiplicative loss, the adversary \r\n
attains the same success probability of breaking the sequentiality of \r\n as the
probability of \r\n breaking the sequentiality of \r\n – a contradiction to the
assumption of the theorem. \r\n\r\nWe believe that the converse implication to
Theorem 2 is not true, i.e., that breaking the sequentiality of \r\n does not necessarily
imply breaking the sequentiality of \r\n. Below, we state it as a conjecture.\r\n\r\nConjecture
1\r\nSequentiality of \r\n cannot be reduced to sequentiality of \r\n.\r\n\r\nOne
reason why the above conjecture might be true is that, while the \r\n delay function
is based solely only on multiplication in the group \r\n, our \r\n delay function
uses the full arithmetic (addition and multiplication) of the commutative ring \r\n.\r\n\r\nOne
way to support the conjecture would be to construct an algorithm that speeds up
iterated squaring but is not immediately applicable to Lucas sequences. By [49]
we know that this cannot be achieved by a generic algorithm. A non-generic algorithm
that solves iterated squaring in time \r\n is presented in [4]. The main tool of
their construction is the Explicit Chinese Remainder Theorem modulo N. However,
a similiar theorem exists also for univariate polynomial rings, which suggests that
a similar speed-up can be obtained for our delay function by adapting the techniques
in [4] to our setting.\r\n\r\n4 VDF from Lucas Sequences\r\nIn Sect. 3.1 we saw
different ways of computing the atomic operation of the delay function. Computing
\r\n in the extension field seems to be the more natural and time and space effective
approach. Furthermore, writing the atomic operation \r\n as \r\n is very clear,
and, thus, we follow this approach throughout the rest of the paper.\r\n\r\n4.1
Structure of \r\nTo construct a VDF based on Lucas sequences, we use an algebraic
extension\r\n\r\n(9)\r\nwhere N is an RSA modulus and \r\n. In this section, we
describe the structure of the algebraic extension given in Expression (9). Based
on our understanding of the structure of the above algebraic extension, we can conclude
that using modulus N composed of safe primes (i.e., for all prime factors p of N,
\r\n has a large prime divisor) is necessary but not sufficient condition for security
of our construction. We specify some sufficient conditions on factors of N in the
subsequent Sect. 4.2.\r\n\r\nFirst, we introduce some simplifying notation for quotient
rings.\r\n\r\nDefinition 9\r\nFor \r\n and \r\n, we denote by \r\n the quotient
ring \r\n, where (m, f(x)) denotes the ideal of the ring \r\n generated by m and
f(x).\r\n\r\nObservation 1, below, allows us to restrict our analysis only to the
structure of \r\n for prime \r\n.\r\n\r\nObservation 1\r\nLet \r\n be distinct primes,
\r\n and \r\n. Then\r\n\r\nProof\r\nUsing the Chinese reminder theorem, we get\r\n\r\nas
claimed. \r\n\r\nThe following lemma characterizes the structure of \r\n with
respect to the discriminant of f. We use \r\n to denote the standard Legendre symbol.\r\n\r\nLemma
1\r\nLet \r\n and \r\n be a polynomial of degree 2 with the discriminant D. Then\r\n\r\nProof\r\nWe
consider each case separately:\r\n\r\nIf \r\n, then f(x) is irreducible over \r\n
and \r\n is a field with \r\n elements. Since \r\n is a finite field, \r\n is cyclic
and contains \r\n elements.\r\n\r\nIf \r\n, then \r\n and f has some double root
\r\n and it can be written as \r\n for some \r\n. Since the ring \r\n is isomorphic
to the ring \r\n (consider the isomorphism \r\n), we can restrict ourselves to describing
the structure of \r\n.\r\n\r\nWe will prove that the function \r\n,\r\n\r\nis an
isomorphism. First, the polynomial \r\n is invertible if and only if \r\n (inverse
is \r\n). For the choice \r\n, we have\r\n\r\nThus \r\n is onto. Second, \r\n is,
in fact, a bijection, because\r\n\r\n(10)\r\nFinally, \r\n is a homomorphism, because\r\n\r\nIf
\r\n, then f(x) has two roots \r\n. We have an isomorphism\r\n\r\nand \r\n. \r\n\r\n4.2
Strong Groups and Strong Primes\r\nTo achieve the verifiability property of our
construction, we need \r\n to contain a strong subgroup (defined next) of order
asymptotically linear in p. We remark that our definition of strong primes is stronger
than the one by Rivest and Silverman [46].\r\n\r\nDefinition 10\r\n(Strong groups).
For \r\n, we say that a non-trivial group \r\n is \r\n-strong, if the order of each
non-trivial subgroup of \r\n is greater than \r\n.\r\n\r\nObservation 2\r\nIf \r\n
and \r\n are \r\n-strong groups, then \r\n is a \r\n-strong group.\r\n\r\nIt can
be seen from Lemma 1 that \r\n always contains groups of small order (e.g. \r\n).
To avoid these, we descend into the subgroup of a-th powers of elements of \r\n.
Below, we introduce the corresponding notation.\r\n\r\nDefinition 11\r\nFor an Abelian
group \r\n and \r\n, we define the subgroup \r\n of \r\n in the multiplicative notation
and \r\n in the additive notation.\r\n\r\nFurther, we show in Lemma 2 below that
\r\n-strong primality (defined next) is a sufficient condition for \r\n to be a
\r\n-strong group.\r\n\r\nDefinition 12\r\n(Strong primes). Let \r\n and \r\n. We
say that p is a \r\n-strong prime, if \r\n and there exists \r\n, \r\n, such that
\r\n and every prime factor of W is greater than \r\n.\r\n\r\nSince a is a public
parameter in our setup, super-polynomial a could reveal partial information about
the factorization of N. However, we could allow a to be polynomial in \r\n while
maintaining hardness of factoring N.Footnote4 For the sake of simplicity of Definition
12, we rather use stronger condition \r\n. The following simple observation will
be useful for proving Lemma 2.\r\n\r\nObservation 3\r\nFor \r\n.\r\n\r\nLemma 2\r\nLet
p be a \r\n-strong prime and \r\n be a quadratic polynomial. Then, \r\n is a \r\n-strong
group.\r\n\r\nProof\r\nFrom definition of the strong primes, there exists \r\n,
whose factors are bigger than \r\n and \r\n. We denote \r\n a factor of W. Applying
Observation 3 to Lemma 1, we get\r\n\r\nIn particular, we used above the fact that
Observation 2 implies that \r\n as explained next. Since \r\n, all divisors of \r\n
are divisors of aW. By definition of a and W in Definition 12, we also have that
\r\n, which implies that any factor of \r\n divides either a or W, but not both.
When we divide \r\n by all the common divisors with a, only the common divisors
with W are left, which implies \r\n. The proof of the lemma is now completed by
Observation 2.\r\n\r\nCorollary 1\r\nLet p be a \r\n-strong prime, q be a \r\n-strong
prime, \r\n, \r\n, \r\n and \r\n. Then \r\n is \r\n-strong.\r\n\r\n4.3 Our Interactive
Protocol\r\nOur interactive protocol is formally described in Fig. 3. To understand
this protocol, we first recall the outline of Pietrzak’s interactive protocol from
Sect. 1.2 and then highlight the hurdles. Let \r\n be an RSA modulus where p and
q are strong primes and let x be a random element from \r\n. The interactive protocol
in [42] allows a prover to convince the verifier of the statement\r\n\r\n“(N, x,
y, T) satisfies \r\n”.\r\n\r\nThe protocol is recursive and in a round-by-round
fashion reduces the claim to a smaller statement by halving the time parameter.
To be precise, in each round the (honest) prover sends the “midpoint” \r\n of the
current statement to the verifier and they together reduce the statement to\r\n\r\n“\r\n
satisfies \r\n”,\r\n\r\nwhere \r\n and \r\n for a random challenge r. This is continued
until \r\n is obtained at which point the verifier simply checks whether \r\n.\r\n\r\nThe
main problem, we face while designing our protocol is ensuring that the verifier
can check whether \r\n sent by prover lies in an appropriate subgroup of \r\n. In
the first draft of Pietrzak’s protocol [41], prover sends a square root of \r\n,
from which the original \r\n can be recovered easily (by simply squaring it) with
a guarantee, that the result lies in a group of quadratic residues \r\n. Notice
that the prover knows the square root of \r\n, because it is just a previous term
in the sequence he computed.\r\n\r\nUsing Pietrzak’s protocol directly for our delay
function would require computing a-th roots in RSA group for some arbitrary a. Since
this is a computationally hard problem, we cannot use the same trick. In fact, the
VDF construction of Wesolowski [54] is based on similar hardness assumption.\r\n\r\nWhile
Pietrzak shifted from \r\n to the group of signed quadratic residues \r\n in his
following paper [42] to get unique proofs, we resort to his old idea of ‘squaring
a square root’ and generalise it.\r\n\r\nThe high level idea is simple. First, on
input \r\n, prover computes the sequence \r\n. Next, during the protocol, verifier
maps all elements sent by the prover by homomorphism\r\n\r\n(11)\r\ninto the target
strong group \r\n. This process is illustrated in Fig. 2. Notice that the equality
\r\n for the original sequence implies the equality \r\n for the mapped sequence
\r\n.\r\n\r\nFig. 2.\r\nfigure 2\r\nIllustration of our computation of the iterated
squaring using the a-th root of \r\n. Horizontal arrows are \r\n and diagonal arrows
are \r\n.\r\n\r\nFull size image\r\nRestriction to Elements of \r\n. Mapping Eq.
(11) introduces a new technical difficulty. Since \r\n is not injective, we narrow
the domain inputs, for which the output of our VDF is verifiable, from \r\n to \r\n.
Furthermore, the only way to verify that a certain x is an element of \r\n is to
get an a-th root of x and raise it to the ath power. So we have to represent elements
of \r\n by elements of \r\n anyway. To resolve these two issues, we introduce a
non-unique representation of elements of \r\n.\r\n\r\nDefinition 13\r\nFor \r\n
and \r\n, we denote \r\n (an element of \r\n) by [x]. Since this representation
of \r\n is not unique, we define an equality relation by\r\n\r\nWe will denote by
tilde () the elements that were already powered to the a by a verifier (i.e. ).
Thus tilded variables verifiably belong to the target group \r\n.\r\n\r\nIn the
following text, the goal of the brackets notation in Definition 13 is to distinguish
places where the equality means the equality of elements of \r\n from those places,
where the equality holds up to \r\n. A reader can also see the notation in Definition
13 as a concrete representation of elements of a factor group \r\n.\r\n\r\nOur security
reduction 2 required the delay function to operate everywhere on \r\n. This is not
a problem if the \r\n algorithm is modified to output the set \r\n.\r\n\r\nFig.
3.\r\nfigure 3\r\nOur Interactive Protocol for \r\n.\r\n\r\nFull size image\r\n4.4
Security\r\nRecall here that \r\n is \r\n-strong group, so there exist\r\n\r\n and
\r\n such that\r\n\r\n(12)\r\nDefinition 14\r\nFor \r\n and \r\n, we define \r\n
as i-th coordinate of \r\n, where \r\n is the isomorphism given by Eq. (12).\r\n\r\nLemma
3\r\nLet \r\n and \r\n. If \r\n, then\r\n\r\n\t(13)\r\nProof\r\nFix \r\n, \r\n and
y. Let some \r\n satisfy\r\n\r\n(14)\r\nUsing notation from Definition 14, we rewrite
Eq. (14) as a set of equations\r\n\r\nFor every \r\n, by reordering the terms, the
j-th equation becomes\r\n\r\n(15)\r\nIf \r\n, then \r\n. Further for every \r\n.
It follows that \r\n. Putting these two equations together gives us \r\n, which
contradicts our assumption \r\n.\r\n\r\nIt follows that there exists \r\n such that\r\n\r\n(16)\r\nThereafter
there exists \r\n such that \r\n divides \r\n and\r\n\r\n(17)\r\nFurthermore, from
Eq. (15), \r\n divides \r\n. Finally, dividing eq. Eq. (15) by \r\n, we get that
r is determined uniquely (\r\n),\r\n\r\nUsing the fact that \r\n, this uniqueness
of r upper bounds number of \r\n, such that Eq. (14) holds, to one. It follows that
the probability that Eq. (14) holds for r chosen randomly from the uniform distribution
over \r\n is less than \r\n. \r\n\r\nCorollary 2\r\nThe halving protocol will
turn an invalid input tuple (i.e. \r\n) into a valid output tuple (i.e. \r\n) with
probability less than \r\n.\r\n\r\nTheorem 3\r\nFor any computationally unbounded
prover who submits anything other than \r\n such that \r\n in phase 2 of the protocol,
the soundness error is upper-bounded by \r\n\r\nProof\r\nIn each round of the protocol,
T decreases to \r\n. It follows that the number of rounds of the halving protocol
before reaching \r\n is upper bounded by \r\n.\r\n\r\nIf the verifier accepts the
solution tuple \r\n in the last round, then the equality \r\n must hold. It follows
that the initial inequality must have turned into equality in some round of the
halving protocol. By Lemma 3, the probability of this event is bounded by \r\n.
Finally, using the union bound for all rounds, we obtain the upper bound (\r\n.
\ \r\n\r\n4.5 Our VDF\r\nAnalogously to the VDF of Pietrzak [42], we compile our
public-coin interactive proof given in Fig. 3 into a VDF using the Fiat-Shamir heuristic.
The complete construction is given in Fig. 4. For ease of exposition, we assume
that the time parameter T is always a power of two.\r\n\r\nFig. 4.\r\nfigure 4\r\n
based on Lucas sequences\r\n\r\nFull size image\r\nAs discussed in Sect. 4.3, it
is crucial for the security of the protocol that the prover computes a sequence
of powers of the a-th root of the challenge and the resulting value (as well as
the intermediate values) received from the prover is lifted to the appropriate group
by raising it to the a-th power. We use the tilde notation in Fig. 4 in order to
denote elements on the sequence relative to the a-th root.\r\n\r\nNote that, by
the construction, the output of our VDF is the \r\n-th power of the root of the
characteristic polynomial for Lucas sequence with parameters P and Q. Therefore,
the value of the delay function implicitly corresponds to the \r\n-th term of the
Lucas sequence.\r\n\r\nTheorem 4\r\nLet \r\n be the statistical security parameter.
The \r\n VDF defined in Fig. 4 is correct and statistically-sound with a negligible
soundness error if \r\n is modelled as a random oracle, against any adversary that
makes \r\n oracle queries.\r\n\r\nProof\r\nThe correctness follows directly by construction.\r\n\r\nTo
prove its statistical soundness, we proceed in a similar way to [42]. We cannot
apply Fiat-Shamir transformation directly, because our protocol does not have constant
number of rounds, thus we use Fiat-Shamir heuristic to each round separately.\r\n\r\nFirst,
we use a random oracle as the \r\n function. Second, if a malicious prover computed
a proof accepted by verifier for some tuple \r\n such that\r\n\r\n(19)\r\nthen he
must have succeeded in turning inequality from Eq. (19) into equality in some round.
By Lemma 3, probability of such a flipping is bounded by \r\n. Every such an attempt
requires one query to random oracle. Using a union bound, it follows that the probability
that a malicious prover who made q queries to random oracle succeeds in flipping
initial inequality into equality in some round is upper-bounded by \r\n.\r\n\r\nSince
q is \r\n, \r\n is a negligible function and thus the soundness error is negligible.
\ \r\n\r\nNotes\r\n1.\r\nNote that integer sequences like Fibonacci numbers and
Mersenne numbers are special cases of Lucas sequences.\r\n\r\n2.\r\nThe choice of
modulus N is said to be safe if \r\n for safe primes \r\n and \r\n, where \r\n and
\r\n are also prime.\r\n\r\n3.\r\nFurther, using the ideas from [14, 20], it is
possible to construct so-called continuous VDFs from Lucas sequences.\r\n\r\n4.\r\nSince
we set a to be at most polynomial in \r\n, its is possible to go over all possible
candidate values for a in time polynomial in \r\n. Thus, any algorithm that could
factor N using the knowledge of a can be efficiently simulated even without the
knowledge of a.\r\n\r\nReferences\r\nAbusalah, H., Kamath, C., Klein, K., Pietrzak,
K., Walter, M.: Reversible proofs of sequential work. In: Ishai, Y., Rijmen, V.
(eds.) EUROCRYPT 2019. LNCS, vol. 11477, pp. 277–291. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17656-3_10\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nAggarwal, D., Maurer, U.: Breaking RSA generically
is equivalent to factoring. IEEE Trans. Inf. Theory 62(11), 6251–6259 (2016). https://doi.org/10.1109/TIT.2016.2594197\r\n\r\nCrossRef\r\n
\r\nMathSciNet\r\n \r\nMATH\r\n \r\nGoogle Scholar\r\n \r\n\r\nArun, A., Bonneau,
J., Clark, J.: Short-lived zero-knowledge proofs and signatures. In: Agrawal, S.,
Lin, D. (eds.) Advances in Cryptology – ASIACRYPT 2022. Lecture Notes in Computer
Science, vol. 13793, pp. 487–516. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-22969-5_17\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nBernstein, D., Sorenson, J.: Modular exponentiation
via the explicit Chinese remainder theorem. Math. Comput. 76, 443–454 (2007). https://doi.org/10.1090/S0025-5718-06-01849-7\r\n\r\nCrossRef\r\n
\r\nMathSciNet\r\n \r\nMATH\r\n \r\nGoogle Scholar\r\n \r\n\r\nBitansky, N., et
al.: PPAD is as hard as LWE and iterated squaring. IACR Cryptol. ePrint Arch., p.
1072 (2022)\r\n\r\nGoogle Scholar\r\n \r\n\r\nBitansky, N., Goldwasser, S., Jain,
A., Paneth, O., Vaikuntanathan, V., Waters, B.: Time-lock puzzles from randomized
encodings. In: ITCS, pp. 345–356. ACM (2016)\r\n\r\nGoogle Scholar\r\n \r\n\r\nBleichenbacher,
D., Bosma, W., Lenstra, A.K.: Some remarks on Lucas-based cryptosystems. In: Coppersmith,
D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 386–396. Springer, Heidelberg (1995).
https://doi.org/10.1007/3-540-44750-4_31\r\n\r\nCrossRef\r\n \r\nGoogle Scholar\r\n
\r\n\r\nBlock, A.R., Holmgren, J., Rosen, A., Rothblum, R.D., Soni, P.: Time- and
space-efficient arguments from groups of unknown order. In: Malkin, T., Peikert,
C. (eds.) CRYPTO 2021. LNCS, vol. 12828, pp. 123–152. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84259-8_5\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nBoneh, D., Bonneau, J., Bünz, B., Fisch, B.: Verifiable
delay functions. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991,
pp. 757–788. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_25\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nBoneh, D., Bünz, B., Fisch, B.: A survey of two verifiable
delay functions. IACR Cryptol. ePrint Arch. 2018, 712 (2018)\r\n\r\nMATH\r\n \r\nGoogle
Scholar\r\n \r\n\r\nBoneh, D., Venkatesan, R.: Breaking RSA may not be equivalent
to factoring. In: Nyberg, K. (ed.) Advances in Cryptology - EUROCRYPT ’98. Lecture
Notes in Computer Science, vol. 1403, pp. 59–71. Springer, Cham (1998). https://doi.org/10.1007/BFb0054117\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nBuchmann, J., Williams, H.C.: A key-exchange system
based on imaginary quadratic fields. J. Cryptol. 1(2), 107–118 (1988). https://doi.org/10.1007/BF02351719\r\n\r\nCrossRef\r\n
\r\nMathSciNet\r\n \r\nMATH\r\n \r\nGoogle Scholar\r\n \r\n\r\nChavez-Saab, J.,
Rodríguez-Henríquez, F., Tibouchi, M.: Verifiable Isogeny walks: towards an isogeny-based
postquantum VDF. In: AlTawy, R., Hülsing, A. (eds.) SAC 2021. LNCS, vol. 13203,
pp. 441–460. Springer, Cham (2022). https://doi.org/10.1007/978-3-030-99277-4_21\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nChoudhuri, A.R., Hubáček, P., Kamath, C., Pietrzak,
K., Rosen, A., Rothblum, G.N.: PPAD-hardness via iterated squaring modulo a composite.
IACR Cryptol. ePrint Arch. 2019, 667 (2019)\r\n\r\nGoogle Scholar\r\n \r\n\r\nCini,
V., Lai, R.W.F., Malavolta, G.: Lattice-based succinct arguments from vanishing
polynomials. In: Handschuh, H., Lysyanskaya, A. (eds.) Advances in Cryptology -
CRYPTO 2023. Lecture Notes in Computer Science, pp. 72–105. Springer Nature Switzerland,
Cham (2023). https://doi.org/10.1007/978-3-031-38545-2_3\r\n\r\nCrossRef\r\n \r\nGoogle
Scholar\r\n \r\n\r\nCohen, B., Pietrzak, K.: Simple proofs of sequential work. In:
Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 451–467.
Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_15\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nCohen, B., Pietrzak, K.: The Chia network blockchain.
Technical report, Chia Network (2019). https://www.chia.net/assets/ChiaGreenPaper.pdf.
Accessed 29 July 2022\r\n\r\nDöttling, N., Garg, S., Malavolta, G., Vasudevan, P.N.:
Tight verifiable delay functions. In: Galdi, C., Kolesnikov, V. (eds.) SCN 2020.
LNCS, vol. 12238, pp. 65–84. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-57990-6_4\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nDöttling, N., Lai, R.W.F., Malavolta, G.: Incremental
proofs of sequential work. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS,
vol. 11477, pp. 292–323. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17656-3_11\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nEphraim, N., Freitag, C., Komargodski, I., Pass,
R.: Continuous verifiable delay functions. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT
2020. LNCS, vol. 12107, pp. 125–154. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45727-3_5\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nDe Feo, L., Masson, S., Petit, C., Sanso, A.: Verifiable
delay functions from supersingular isogenies and pairings. In: Galbraith, S.D.,
Moriai, S. (eds.) ASIACRYPT 2019. LNCS, vol. 11921, pp. 248–277. Springer, Cham
(2019). https://doi.org/10.1007/978-3-030-34578-5_10\r\n\r\nCrossRef\r\n \r\nGoogle
Scholar\r\n \r\n\r\nFiat, A., Shamir, A.: How to prove yourself: practical solutions
to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS,
vol. 263, pp. 186–194. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-47721-7_12\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nFreitag, C., Pass, R., Sirkin, N.: Parallelizable
delegation from LWE. IACR Cryptol. ePrint Arch., p. 1025 (2022)\r\n\r\nGoogle Scholar\r\n
\r\n\r\nGoldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive
proof systems. SIAM J. Comput. 18(1), 186–208 (1989)\r\n\r\nCrossRef\r\n \r\nMathSciNet\r\n
\r\nMATH\r\n \r\nGoogle Scholar\r\n \r\n\r\nHoffmann, C., Hubáček, P., Kamath, C.,
Klein, K., Pietrzak, K.: Practical statistically sound proofs of exponentiation
in any group. In: Dodis, Y., Shrimpton, T. (eds.) Advances in Cryptology – CRYPTO
2022. Lecture Notes in Computer Science, vol. 13508, pp. 1–30. Springer, Cham (2022).
https://doi.org/10.1007/978-3-031-15979-4_13\r\n\r\nCrossRef\r\n \r\nMATH\r\n \r\nGoogle
Scholar\r\n \r\n\r\nHofheinz, D., Kiltz, E.: The group of signed quadratic residues
and applications. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 637–653.
Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03356-8_37\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nKatz, J., Loss, J., Xu, J.: On the security of time-lock
puzzles and timed commitments. In: Pass, R., Pietrzak, K. (eds.) TCC 2020, Part
III. LNCS, vol. 12552, pp. 390–413. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64381-2_14\r\n\r\nCrossRef\r\n
\r\nMATH\r\n \r\nGoogle Scholar\r\n \r\n\r\nLai, R.W.F., Malavolta, G.: Lattice-based
timed cryptography. In: Handschuh, H., Lysyanskaya, A. (eds.) Advances in Cryptology
- CRYPTO 2023. Lecture Notes in Computer Science, pp. 782–804. Springer Nature Switzerland,
Cham (2023). https://doi.org/10.1007/978-3-031-38554-4_25\r\n\r\nCrossRef\r\n \r\nGoogle
Scholar\r\n \r\n\r\nLehmer, D.H.: An extended theory of Lucas’ functions. Ann. Math.
31(3), 419–448 (1930). https://www.jstor.org/stable/1968235\r\n\r\nLennon, M.J.J.,
Smith, P.J.: LUC: A new public key system. In: Douglas, E.G. (ed.) Ninth IFIP Symposium
on Computer Security, pp. 103–117. Elsevier Science Publishers (1993)\r\n\r\nGoogle
Scholar\r\n \r\n\r\nLenstra, A.K., Wesolowski, B.: Trustworthy public randomness
with sloth, unicorn, and trx. IJACT 3(4), 330–343 (2017)\r\n\r\nCrossRef\r\n \r\nMathSciNet\r\n
\r\nMATH\r\n \r\nGoogle Scholar\r\n \r\n\r\nLipmaa, H.: On Diophantine complexity
and statistical zero-knowledge arguments. In: Laih, C.-S. (ed.) ASIACRYPT 2003.
LNCS, vol. 2894, pp. 398–415. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-40061-5_26\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nLombardi, A., Vaikuntanathan, V.: Fiat-Shamir for
repeated squaring with applications to PPAD-hardness and VDFs. In: Micciancio, D.,
Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12172, pp. 632–651. Springer, Cham
(2020). https://doi.org/10.1007/978-3-030-56877-1_22\r\n\r\nCrossRef\r\n \r\nGoogle
Scholar\r\n \r\n\r\nLucas, E.: Théorie des fonctions numériques simplement périodiques.
Am. J. Math. 1(4), 289–321 (1878). https://www.jstor.org/stable/2369373\r\n\r\nLund,
C., Fortnow, L., Karloff, H.J., Nisan, N.: Algebraic methods for interactive proof
systems. J. ACM 39(4), 859–868 (1992)\r\n\r\nCrossRef\r\n \r\nMathSciNet\r\n \r\nMATH\r\n
\r\nGoogle Scholar\r\n \r\n\r\nMahmoody, M., Moran, T., Vadhan, S.P.: Publicly verifiable
proofs of sequential work. In: ITCS, pp. 373–388. ACM (2013)\r\n\r\nGoogle Scholar\r\n
\r\n\r\nMahmoody, M., Smith, C., Wu, D.J.: A note on the (Im)possibility of verifiable
delay functions in the random oracle model. IACR Cryptol. ePrint Arch. 2019, 663
(2019)\r\n\r\nGoogle Scholar\r\n \r\n\r\nMalavolta, G., Thyagarajan, S.A.K.: Homomorphic
time-lock puzzles and applications. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO
2019. LNCS, vol. 11692, pp. 620–649. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_22\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nMüller, W.B., Nöbauer, W.: Some remarks on public-key
cryptosystems. Studia Sci. Math. Hungar. 16, 71–76 (1981)\r\n\r\nMathSciNet\r\n
\r\nMATH\r\n \r\nGoogle Scholar\r\n \r\n\r\nBressoud, D.M.: Factorization and primality
testing. Math. Comput. 56(193), 400 (1991)\r\n\r\nCrossRef\r\n \r\nGoogle Scholar\r\n
\r\n\r\nPietrzak, K.: Simple verifiable delay functions. IACR Cryptol. ePrint Arch.
2018, 627 (2018). https://eprint.iacr.org/2018/627/20180720:081000\r\n\r\nPietrzak,
K.: Simple verifiable delay functions. In: ITCS. LIPIcs, vol. 124, pp. 1–15. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik (2019)\r\n\r\nGoogle Scholar\r\n \r\n\r\nRabin,
M.O.: Transaction protection by beacons. J. Comput. Syst. Sci. 27(2), 256–267 (1983)\r\n\r\nCrossRef\r\n
\r\nMathSciNet\r\n \r\nMATH\r\n \r\nGoogle Scholar\r\n \r\n\r\nRibenboim, P.: My
Numbers, My Friends: Popular Lectures on Number Theory. Springer-Verlag, New York
(2000)\r\n\r\nCrossRef\r\n \r\nMATH\r\n \r\nGoogle Scholar\r\n \r\n\r\nRiesel, H.:
Prime Numbers and Computer Methods for Factorization, Progress in Mathematics, vol.
57. Birkhäuser, Basel (1985)\r\n\r\nCrossRef\r\n \r\nMATH\r\n \r\nGoogle Scholar\r\n
\r\n\r\nRivest, R., Silverman, R.: Are ’strong’ primes needed for RSA. Cryptology
ePrint Archive, Report 2001/007 (2001). https://eprint.iacr.org/2001/007\r\n\r\nRivest,
R.L., Shamir, A., Adleman, L.M.: A method for obtaining digital signatures and public-key
cryptosystems (reprint). Commun. ACM 26(1), 96–99 (1983)\r\n\r\nCrossRef\r\n \r\nMATH\r\n
\r\nGoogle Scholar\r\n \r\n\r\nRivest, R.L., Shamir, A., Wagner, D.A.: Time-lock
puzzles and timed-release crypto. Technical report, Massachusetts Institute of Technology
(1996)\r\n\r\nGoogle Scholar\r\n \r\n\r\nRotem, L., Segev, G.: Generically speeding-up
repeated squaring is equivalent to factoring: sharp thresholds for all generic-ring
delay functions. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol.
12172, pp. 481–509. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56877-1_17\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nRotem, L., Segev, G., Shahaf, I.: Generic-group delay
functions require hidden-order groups. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT
2020. LNCS, vol. 12107, pp. 155–180. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45727-3_6\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nSchindler, P., Judmayer, A., Hittmeir, M., Stifter,
N., Weippl, E.R.: RandRunner: distributed randomness from trapdoor VDFs with strong
uniqueness. In: 28th Annual Network and Distributed System Security Symposium, NDSS
2021, virtually, 21–25 February 2021. The Internet Society (2021)\r\n\r\nGoogle
Scholar\r\n \r\n\r\nShani, B.: A note on isogeny-based hybrid verifiable delay functions.
IACR Cryptol. ePrint Arch. 2019, 205 (2019)\r\n\r\nGoogle Scholar\r\n \r\n\r\nValiant,
P.: Incrementally verifiable computation or proofs of knowledge imply time/space
efficiency. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 1–18. Springer,
Heidelberg (2008). https://doi.org/10.1007/978-3-540-78524-8_1\r\n\r\nCrossRef\r\n
\r\nMATH\r\n \r\nGoogle Scholar\r\n \r\n\r\nWesolowski, B.: Efficient verifiable
delay functions. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11478,
pp. 379–407. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17659-4_13\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nWesolowski, B.: Efficient verifiable delay functions.
J. Cryptol. 33(4), 2113–2147 (2020). https://doi.org/10.1007/s00145-020-09364-x\r\n\r\nCrossRef\r\n
\r\nMathSciNet\r\n \r\nMATH\r\n \r\nGoogle Scholar\r\n \r\n\r\nWilliams, H.C.: A
\r\n method of factoring. Math. Comput. 39(159), 225–234 (1982)\r\n\r\nMathSciNet\r\n
\r\nMATH\r\n \r\nGoogle Scholar\r\n \r\n\r\nWilliams, H.C.: Édouard lucas and primality
testing. Math. Gaz. 83, 173 (1999)\r\n\r\nCrossRef\r\n \r\nGoogle Scholar\r\n \r\n\r\nDownload
references\r\n\r\nAcknowledgements\r\nWe thank Krzysztof Pietrzak and Alon Rosen
for several fruitful discussions about this work and the anonymous reviewers of
SCN 2022 and TCC 2023 for valuable suggestions.\r\n\r\nPavel Hubáček is supported
by the Czech Academy of Sciences (RVO 67985840), by the Grant Agency of the Czech
Republic under the grant agreement no. 19-27871X, and by the Charles University
project UNCE/SCI/004. Chethan Kamath is supported by Azrieli International Postdoctoral
Fellowship, by the European Research Council (ERC) under the European Union’s Horizon
Europe research and innovation programme (grant agreement No. 101042417, acronym
SPP), and by ISF grant 1789/19."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Charlotte
full_name: Hoffmann, Charlotte
id: 0f78d746-dc7d-11ea-9b2f-83f92091afe7
last_name: Hoffmann
orcid: 0000-0003-2027-5549
- first_name: Pavel
full_name: Hubáček, Pavel
last_name: Hubáček
- first_name: Chethan
full_name: Kamath, Chethan
last_name: Kamath
- first_name: Tomáš
full_name: Krňák, Tomáš
last_name: Krňák
citation:
ama: 'Hoffmann C, Hubáček P, Kamath C, Krňák T. (Verifiable) delay functions from
Lucas sequences. In: 21st International Conference on Theory of Cryptography.
Vol 14372. Springer Nature; 2023:336-362. doi:10.1007/978-3-031-48624-1_13'
apa: 'Hoffmann, C., Hubáček, P., Kamath, C., & Krňák, T. (2023). (Verifiable)
delay functions from Lucas sequences. In 21st International Conference on Theory
of Cryptography (Vol. 14372, pp. 336–362). Taipei, Taiwan: Springer Nature.
https://doi.org/10.1007/978-3-031-48624-1_13'
chicago: Hoffmann, Charlotte, Pavel Hubáček, Chethan Kamath, and Tomáš Krňák. “(Verifiable)
Delay Functions from Lucas Sequences.” In 21st International Conference on
Theory of Cryptography, 14372:336–62. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-48624-1_13.
ieee: C. Hoffmann, P. Hubáček, C. Kamath, and T. Krňák, “(Verifiable) delay functions
from Lucas sequences,” in 21st International Conference on Theory of Cryptography,
Taipei, Taiwan, 2023, vol. 14372, pp. 336–362.
ista: 'Hoffmann C, Hubáček P, Kamath C, Krňák T. 2023. (Verifiable) delay functions
from Lucas sequences. 21st International Conference on Theory of Cryptography.
TCC: Theory of Cryptography, LNCS, vol. 14372, 336–362.'
mla: Hoffmann, Charlotte, et al. “(Verifiable) Delay Functions from Lucas Sequences.”
21st International Conference on Theory of Cryptography, vol. 14372, Springer
Nature, 2023, pp. 336–62, doi:10.1007/978-3-031-48624-1_13.
short: C. Hoffmann, P. Hubáček, C. Kamath, T. Krňák, in:, 21st International Conference
on Theory of Cryptography, Springer Nature, 2023, pp. 336–362.
conference:
end_date: 2023-12-02
location: Taipei, Taiwan
name: 'TCC: Theory of Cryptography'
start_date: 2023-11-29
date_created: 2023-12-17T23:00:54Z
date_published: 2023-11-27T00:00:00Z
date_updated: 2023-12-18T09:00:00Z
day: '27'
department:
- _id: KrPi
doi: 10.1007/978-3-031-48624-1_13
intvolume: ' 14372'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2023/1404
month: '11'
oa: 1
oa_version: Preprint
page: 336-362
publication: 21st International Conference on Theory of Cryptography
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031486234'
issn:
- 0302-9743
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: (Verifiable) delay functions from Lucas sequences
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 14372
year: '2023'
...
---
_id: '14703'
abstract:
- lang: eng
text: We present a discretization of the dynamic optimal transport problem for which
we can obtain the convergence rate for the value of the transport cost to its
continuous value when the temporal and spatial stepsize vanish. This convergence
result does not require any regularity assumption on the measures, though experiments
suggest that the rate is not sharp. Via an analysis of the duality gap we also
obtain the convergence rates for the gradient of the optimal potentials and the
velocity field under mild regularity assumptions. To obtain such rates we discretize
the dual formulation of the dynamic optimal transport problem and use the mature
literature related to the error due to discretizing the Hamilton-Jacobi equation.
acknowledgement: "The authors would like to thank Chris Wojtan for his continuous
support and several interesting discussions. Part of this research was performed
during two visits: one of SI to the BIDSA research center at Bocconi University,
and one of HL to the Institute of Science and Technology Austria. Both host institutions
are warmly acknowledged for the hospital-\r\nity. HL is partially supported by the
MUR-Prin 2022-202244A7YL “Gradient Flows and Non-Smooth Geometric Structures with
Applications to Optimization and Machine Learning”, funded by the European Union
- Next Generation EU. SI is supported in part by ERC Consolidator Grant 101045083
“CoDiNA” funded by the European Research Council."
article_number: '2312.12213'
article_processing_charge: No
arxiv: 1
author:
- first_name: Sadashige
full_name: Ishida, Sadashige
id: 6F7C4B96-A8E9-11E9-A7CA-09ECE5697425
last_name: Ishida
- first_name: Hugo
full_name: Lavenant, Hugo
last_name: Lavenant
citation:
ama: Ishida S, Lavenant H. Quantitative convergence of a discretization of dynamic
optimal transport using the dual formulation. arXiv. doi:10.48550/arXiv.2312.12213
apa: Ishida, S., & Lavenant, H. (n.d.). Quantitative convergence of a discretization
of dynamic optimal transport using the dual formulation. arXiv. https://doi.org/10.48550/arXiv.2312.12213
chicago: Ishida, Sadashige, and Hugo Lavenant. “Quantitative Convergence of a Discretization
of Dynamic Optimal Transport Using the Dual Formulation.” ArXiv, n.d. https://doi.org/10.48550/arXiv.2312.12213.
ieee: S. Ishida and H. Lavenant, “Quantitative convergence of a discretization of
dynamic optimal transport using the dual formulation,” arXiv. .
ista: Ishida S, Lavenant H. Quantitative convergence of a discretization of dynamic
optimal transport using the dual formulation. arXiv, 2312.12213.
mla: Ishida, Sadashige, and Hugo Lavenant. “Quantitative Convergence of a Discretization
of Dynamic Optimal Transport Using the Dual Formulation.” ArXiv, 2312.12213,
doi:10.48550/arXiv.2312.12213.
short: S. Ishida, H. Lavenant, ArXiv (n.d.).
date_created: 2023-12-21T10:14:37Z
date_published: 2023-12-19T00:00:00Z
date_updated: 2023-12-27T13:44:33Z
day: '19'
department:
- _id: GradSch
- _id: ChWo
doi: 10.48550/arXiv.2312.12213
external_id:
arxiv:
- '2312.12213'
keyword:
- Optimal transport
- Hamilton-Jacobi equation
- convex optimization
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2312.12213
month: '12'
oa: 1
oa_version: Preprint
project:
- _id: 34bc2376-11ca-11ed-8bc3-9a3b3961a088
grant_number: '101045083'
name: Computational Discovery of Numerical Algorithms for Animation and Simulation
of Natural Phenomena
publication: arXiv
publication_status: submitted
status: public
title: Quantitative convergence of a discretization of dynamic optimal transport using
the dual formulation
type: preprint
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2023'
...
---
_id: '14709'
abstract:
- lang: eng
text: Amid the delays due to the global pandemic, in early October 2022, the auxin
community gathered in the idyllic peninsula of Cavtat, Croatia. More than 170
scientists from across the world converged to discuss the latest advancements
in fundamental and applied research in the field. The topics, from signalling
and transport to plant architecture and response to the environment, show how
auxin research must bridge from the molecular realm to macroscopic developmental
responses. This is mirrored in this collection of reviews, contributed by participants
of the Auxin 2022 meeting.
article_processing_charge: Yes (in subscription journal)
article_type: original
author:
- first_name: Marta
full_name: Del Bianco, Marta
last_name: Del Bianco
- first_name: Jiří
full_name: Friml, Jiří
id: 4159519E-F248-11E8-B48F-1D18A9856A87
last_name: Friml
orcid: 0000-0002-8302-7596
- first_name: Lucia
full_name: Strader, Lucia
last_name: Strader
- first_name: Stefan
full_name: Kepinski, Stefan
last_name: Kepinski
citation:
ama: 'Del Bianco M, Friml J, Strader L, Kepinski S. Auxin research: Creating tools
for a greener future. Journal of Experimental Botany. 2023;74(22):6889-6892.
doi:10.1093/jxb/erad420'
apa: 'Del Bianco, M., Friml, J., Strader, L., & Kepinski, S. (2023). Auxin research:
Creating tools for a greener future. Journal of Experimental Botany. Oxford
University Press. https://doi.org/10.1093/jxb/erad420'
chicago: 'Del Bianco, Marta, Jiří Friml, Lucia Strader, and Stefan Kepinski. “Auxin
Research: Creating Tools for a Greener Future.” Journal of Experimental Botany.
Oxford University Press, 2023. https://doi.org/10.1093/jxb/erad420.'
ieee: 'M. Del Bianco, J. Friml, L. Strader, and S. Kepinski, “Auxin research: Creating
tools for a greener future,” Journal of Experimental Botany, vol. 74, no.
22. Oxford University Press, pp. 6889–6892, 2023.'
ista: 'Del Bianco M, Friml J, Strader L, Kepinski S. 2023. Auxin research: Creating
tools for a greener future. Journal of Experimental Botany. 74(22), 6889–6892.'
mla: 'Del Bianco, Marta, et al. “Auxin Research: Creating Tools for a Greener Future.”
Journal of Experimental Botany, vol. 74, no. 22, Oxford University Press,
2023, pp. 6889–92, doi:10.1093/jxb/erad420.'
short: M. Del Bianco, J. Friml, L. Strader, S. Kepinski, Journal of Experimental
Botany 74 (2023) 6889–6892.
date_created: 2023-12-24T23:00:53Z
date_published: 2023-12-01T00:00:00Z
date_updated: 2024-01-02T09:29:24Z
day: '01'
ddc:
- '580'
department:
- _id: JiFr
doi: 10.1093/jxb/erad420
external_id:
pmid:
- '38038239'
file:
- access_level: open_access
checksum: f66fb960fd791dea53fd0e087f2fbbe8
content_type: application/pdf
creator: dernst
date_created: 2024-01-02T09:23:57Z
date_updated: 2024-01-02T09:23:57Z
file_id: '14724'
file_name: 2023_JourExperimentalBotany_DelBianco.pdf
file_size: 425194
relation: main_file
success: 1
file_date_updated: 2024-01-02T09:23:57Z
has_accepted_license: '1'
intvolume: ' 74'
issue: '22'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: 6889-6892
pmid: 1
publication: Journal of Experimental Botany
publication_identifier:
eissn:
- 1460-2431
issn:
- 0022-0957
publication_status: published
publisher: Oxford University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Auxin research: Creating tools for a greener future'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 74
year: '2023'
...
---
_id: '14710'
abstract:
- lang: eng
text: The self-assembly of complex structures from a set of non-identical building
blocks is a hallmark of soft matter and biological systems, including protein
complexes, colloidal clusters, and DNA-based assemblies. Predicting the dependence
of the equilibrium assembly yield on the concentrations and interaction energies
of building blocks is highly challenging, owing to the difficulty of computing
the entropic contributions to the free energy of the many structures that compete
with the ground state configuration. While these calculations yield well known
results for spherically symmetric building blocks, they do not hold when the building
blocks have internal rotational degrees of freedom. Here we present an approach
for solving this problem that works with arbitrary building blocks, including
proteins with known structure and complex colloidal building blocks. Our algorithm
combines classical statistical mechanics with recently developed computational
tools for automatic differentiation. Automatic differentiation allows efficient
evaluation of equilibrium averages over configurations that would otherwise be
intractable. We demonstrate the validity of our framework by comparison to molecular
dynamics simulations of simple examples, and apply it to calculate the yield curves
for known protein complexes and for the assembly of colloidal shells.
acknowledgement: 'We thank Lucy Colwell for suggesting that we use covariance based
methods to predict contacts and Yang Hsia, Scott Boyken, Zibo Chen, and David Baker
for collaborations on designed protein complexes. We also thank Ned Wingreen for
suggesting the alternative derivation of (11). This research was supported by the
Office of Naval Research through ONR N00014-17-1-3029, the Simons Foundation the
NSF-Simons Center for Mathematical and Statistical Analysis of Biology at Harvard
(award number #1764269), the Peter B. Lewis ’55 Lewis-Sigler Institute/Genomics
Fund through the Lewis-Sigler Institute of Integrative Genomics at Princeton University,
and the National Science Foundation through the Center for the Physics of Biological
Function (PHY-1734030).'
article_number: '8328'
article_processing_charge: Yes
article_type: original
author:
- first_name: Agnese I.
full_name: Curatolo, Agnese I.
last_name: Curatolo
- first_name: Ofer
full_name: Kimchi, Ofer
last_name: Kimchi
- first_name: Carl Peter
full_name: Goodrich, Carl Peter
id: EB352CD2-F68A-11E9-89C5-A432E6697425
last_name: Goodrich
orcid: 0000-0002-1307-5074
- first_name: Ryan K.
full_name: Krueger, Ryan K.
last_name: Krueger
- first_name: Michael P.
full_name: Brenner, Michael P.
last_name: Brenner
citation:
ama: Curatolo AI, Kimchi O, Goodrich CP, Krueger RK, Brenner MP. A computational
toolbox for the assembly yield of complex and heterogeneous structures. Nature
Communications. 2023;14. doi:10.1038/s41467-023-43168-4
apa: Curatolo, A. I., Kimchi, O., Goodrich, C. P., Krueger, R. K., & Brenner,
M. P. (2023). A computational toolbox for the assembly yield of complex and heterogeneous
structures. Nature Communications. Springer Nature. https://doi.org/10.1038/s41467-023-43168-4
chicago: Curatolo, Agnese I., Ofer Kimchi, Carl Peter Goodrich, Ryan K. Krueger,
and Michael P. Brenner. “A Computational Toolbox for the Assembly Yield of Complex
and Heterogeneous Structures.” Nature Communications. Springer Nature,
2023. https://doi.org/10.1038/s41467-023-43168-4.
ieee: A. I. Curatolo, O. Kimchi, C. P. Goodrich, R. K. Krueger, and M. P. Brenner,
“A computational toolbox for the assembly yield of complex and heterogeneous structures,”
Nature Communications, vol. 14. Springer Nature, 2023.
ista: Curatolo AI, Kimchi O, Goodrich CP, Krueger RK, Brenner MP. 2023. A computational
toolbox for the assembly yield of complex and heterogeneous structures. Nature
Communications. 14, 8328.
mla: Curatolo, Agnese I., et al. “A Computational Toolbox for the Assembly Yield
of Complex and Heterogeneous Structures.” Nature Communications, vol. 14,
8328, Springer Nature, 2023, doi:10.1038/s41467-023-43168-4.
short: A.I. Curatolo, O. Kimchi, C.P. Goodrich, R.K. Krueger, M.P. Brenner, Nature
Communications 14 (2023).
date_created: 2023-12-24T23:00:53Z
date_published: 2023-12-01T00:00:00Z
date_updated: 2024-01-02T11:36:46Z
day: '01'
ddc:
- '530'
department:
- _id: CaGo
doi: 10.1038/s41467-023-43168-4
file:
- access_level: open_access
checksum: fd9e9d527c2691f03fbc24031a75a3b3
content_type: application/pdf
creator: kschuh
date_created: 2023-12-27T08:40:43Z
date_updated: 2023-12-27T08:40:43Z
file_id: '14714'
file_name: 2023_NatureComm_Curatolo.pdf
file_size: 1342319
relation: main_file
success: 1
file_date_updated: 2023-12-27T08:40:43Z
has_accepted_license: '1'
intvolume: ' 14'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
publication: Nature Communications
publication_identifier:
eissn:
- '20411723'
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: A computational toolbox for the assembly yield of complex and heterogeneous
structures
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 14
year: '2023'
...
---
_id: '14715'
abstract:
- lang: eng
text: We consider N trapped bosons in the mean-field limit with coupling constant
λN = 1/(N − 1). The ground state of such systems exhibits Bose–Einstein condensation.
We prove that the probability of finding ℓ particles outside the condensate wave
function decays exponentially in ℓ.
acknowledgement: We thank Lea Boßmann, Phan Thành Nam and Simone Rademacher for helpful
remarks. P.P. acknowledges funding by the Deutsche Forschungsgemeinschaft (DFG,
German Research Foundation) - Grant No. SFB/TRR 352 “Mathematics of Many-Body Quantum
Systems and Their Collective Phenomena.”
article_number: '121901'
article_processing_charge: Yes (in subscription journal)
article_type: original
arxiv: 1
author:
- first_name: David Johannes
full_name: Mitrouskas, David Johannes
id: cbddacee-2b11-11eb-a02e-a2e14d04e52d
last_name: Mitrouskas
- first_name: Peter
full_name: Pickl, Peter
last_name: Pickl
citation:
ama: Mitrouskas DJ, Pickl P. Exponential decay of the number of excitations in the
weakly interacting Bose gas. Journal of Mathematical Physics. 2023;64(12).
doi:10.1063/5.0172199
apa: Mitrouskas, D. J., & Pickl, P. (2023). Exponential decay of the number
of excitations in the weakly interacting Bose gas. Journal of Mathematical
Physics. AIP Publishing. https://doi.org/10.1063/5.0172199
chicago: Mitrouskas, David Johannes, and Peter Pickl. “Exponential Decay of the
Number of Excitations in the Weakly Interacting Bose Gas.” Journal of Mathematical
Physics. AIP Publishing, 2023. https://doi.org/10.1063/5.0172199.
ieee: D. J. Mitrouskas and P. Pickl, “Exponential decay of the number of excitations
in the weakly interacting Bose gas,” Journal of Mathematical Physics, vol.
64, no. 12. AIP Publishing, 2023.
ista: Mitrouskas DJ, Pickl P. 2023. Exponential decay of the number of excitations
in the weakly interacting Bose gas. Journal of Mathematical Physics. 64(12), 121901.
mla: Mitrouskas, David Johannes, and Peter Pickl. “Exponential Decay of the Number
of Excitations in the Weakly Interacting Bose Gas.” Journal of Mathematical
Physics, vol. 64, no. 12, 121901, AIP Publishing, 2023, doi:10.1063/5.0172199.
short: D.J. Mitrouskas, P. Pickl, Journal of Mathematical Physics 64 (2023).
date_created: 2023-12-31T23:01:02Z
date_published: 2023-12-01T00:00:00Z
date_updated: 2024-01-02T08:51:28Z
day: '01'
ddc:
- '510'
department:
- _id: RoSe
doi: 10.1063/5.0172199
external_id:
arxiv:
- '2307.11062'
file:
- access_level: open_access
checksum: 66572f718a36465576cf0d6b3f7e01fc
content_type: application/pdf
creator: dernst
date_created: 2024-01-02T08:45:07Z
date_updated: 2024-01-02T08:45:07Z
file_id: '14722'
file_name: 2023_JourMathPhysics_Mitrouskas.pdf
file_size: 4346922
relation: main_file
success: 1
file_date_updated: 2024-01-02T08:45:07Z
has_accepted_license: '1'
intvolume: ' 64'
issue: '12'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
publication: Journal of Mathematical Physics
publication_identifier:
eissn:
- 1089-7658
issn:
- 0022-2488
publication_status: published
publisher: AIP Publishing
quality_controlled: '1'
scopus_import: '1'
status: public
title: Exponential decay of the number of excitations in the weakly interacting Bose
gas
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 64
year: '2023'
...
---
_id: '14716'
abstract:
- lang: eng
text: "Background: Antimicrobial resistance (AMR) poses a significant global health
threat, and an accurate prediction of bacterial resistance patterns is critical
for effective treatment and control strategies. In recent years, machine learning
(ML) approaches have emerged as powerful tools for analyzing large-scale bacterial
AMR data. However, ML methods often ignore evolutionary relationships among bacterial
strains, which can greatly impact performance of the ML methods, especially if
resistance-associated features are attempted to be detected. Genome-wide association
studies (GWAS) methods like linear mixed models accounts for the evolutionary
relationships in bacteria, but they uncover only highly significant variants which
have already been reported in literature.\r\n\r\nResults: In this work, we introduce
a novel phylogeny-related parallelism score (PRPS), which measures whether a certain
feature is correlated with the population structure of a set of samples. We demonstrate
that PRPS can be used, in combination with SVM- and random forest-based models,
to reduce the number of features in the analysis, while simultaneously increasing
models’ performance. We applied our pipeline to publicly available AMR data from
PATRIC database for Mycobacterium tuberculosis against six common antibiotics.\r\n\r\nConclusions:
Using our pipeline, we re-discovered known resistance-associated mutations as
well as new candidate mutations which can be related to resistance and not previously
reported in the literature. We demonstrated that taking into account phylogenetic
relationships not only improves the model performance, but also yields more biologically
relevant predicted most contributing resistance markers."
acknowledgement: Open Access funding enabled and organized by Projekt DEAL. A.Y. and
O.V.K. acknowledge financial support from the Klaus Faber Foundation. A.A.A. was
funded by the Helmholtz AI project AMR-XAI. The work of O.O.B. is funded by Fonds
zur Förderung der Wissenschaftlichen Forschung (FWF), Grant ESP 253-B.
article_number: '404'
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Alper
full_name: Yurtseven, Alper
last_name: Yurtseven
- first_name: Sofia
full_name: Buyanova, Sofia
id: 2F54A7BC-3902-11EA-AC87-BC9F3DDC885E
last_name: Buyanova
- first_name: Amay Ajaykumar A.
full_name: Agrawal, Amay Ajaykumar A.
last_name: Agrawal
- first_name: Olga
full_name: Bochkareva, Olga
id: C4558D3C-6102-11E9-A62E-F418E6697425
last_name: Bochkareva
orcid: 0000-0003-1006-6639
- first_name: Olga V V.
full_name: Kalinina, Olga V V.
last_name: Kalinina
citation:
ama: Yurtseven A, Buyanova S, Agrawal AAA, Bochkareva O, Kalinina OVV. Machine learning
and phylogenetic analysis allow for predicting antibiotic resistance in M. tuberculosis.
BMC Microbiology. 2023;23(1). doi:10.1186/s12866-023-03147-7
apa: Yurtseven, A., Buyanova, S., Agrawal, A. A. A., Bochkareva, O., & Kalinina,
O. V. V. (2023). Machine learning and phylogenetic analysis allow for predicting
antibiotic resistance in M. tuberculosis. BMC Microbiology. Springer Nature.
https://doi.org/10.1186/s12866-023-03147-7
chicago: Yurtseven, Alper, Sofia Buyanova, Amay Ajaykumar A. Agrawal, Olga Bochkareva,
and Olga V V. Kalinina. “Machine Learning and Phylogenetic Analysis Allow for
Predicting Antibiotic Resistance in M. Tuberculosis.” BMC Microbiology.
Springer Nature, 2023. https://doi.org/10.1186/s12866-023-03147-7.
ieee: A. Yurtseven, S. Buyanova, A. A. A. Agrawal, O. Bochkareva, and O. V. V. Kalinina,
“Machine learning and phylogenetic analysis allow for predicting antibiotic resistance
in M. tuberculosis,” BMC Microbiology, vol. 23, no. 1. Springer Nature,
2023.
ista: Yurtseven A, Buyanova S, Agrawal AAA, Bochkareva O, Kalinina OVV. 2023. Machine
learning and phylogenetic analysis allow for predicting antibiotic resistance
in M. tuberculosis. BMC Microbiology. 23(1), 404.
mla: Yurtseven, Alper, et al. “Machine Learning and Phylogenetic Analysis Allow
for Predicting Antibiotic Resistance in M. Tuberculosis.” BMC Microbiology,
vol. 23, no. 1, 404, Springer Nature, 2023, doi:10.1186/s12866-023-03147-7.
short: A. Yurtseven, S. Buyanova, A.A.A. Agrawal, O. Bochkareva, O.V.V. Kalinina,
BMC Microbiology 23 (2023).
date_created: 2023-12-31T23:01:02Z
date_published: 2023-12-01T00:00:00Z
date_updated: 2024-01-02T09:20:57Z
day: '01'
ddc:
- '570'
department:
- _id: FyKo
doi: 10.1186/s12866-023-03147-7
external_id:
pmid:
- '38124060'
file:
- access_level: open_access
checksum: 7ff5e95f3496ff663301eb4a13a316d5
content_type: application/pdf
creator: dernst
date_created: 2024-01-02T09:09:32Z
date_updated: 2024-01-02T09:09:32Z
file_id: '14723'
file_name: 2023_BMCMicrobiology_Yurtseven.pdf
file_size: 1979922
relation: main_file
success: 1
file_date_updated: 2024-01-02T09:09:32Z
has_accepted_license: '1'
intvolume: ' 23'
issue: '1'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
pmid: 1
publication: BMC Microbiology
publication_identifier:
eissn:
- 1471-2180
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Machine learning and phylogenetic analysis allow for predicting antibiotic
resistance in M. tuberculosis
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 23
year: '2023'
...
---
_id: '14717'
abstract:
- lang: eng
text: We count primitive lattices of rank d inside Zn as their covolume tends to
infinity, with respect to certain parameters of such lattices. These parameters
include, for example, the subspace that a lattice spans, namely its projection
to the Grassmannian; its homothety class and its equivalence class modulo rescaling
and rotation, often referred to as a shape. We add to a prior work of Schmidt
by allowing sets in the spaces of parameters that are general enough to conclude
the joint equidistribution of these parameters. In addition to the primitive d-lattices
Λ themselves, we also consider their orthogonal complements in Zn, A1, and show
that the equidistribution occurs jointly for Λ and A1. Finally, our asymptotic
formulas for the number of primitive lattices include an explicit bound on the
error term.
acknowledgement: This work was done when both authors were visiting Institute of Science
and Technology (IST) Austria. T.H. was being supported by Engineering and Physical
Sciences Research Council grant EP/P026710/1. Y.K. had a great time there and is
grateful for the hospitality. The appendix to this paper is largely based on a mini
course T.H. had given at IST in February 2020.
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Tal
full_name: Horesh, Tal
id: C8B7BF48-8D81-11E9-BCA9-F536E6697425
last_name: Horesh
- first_name: Yakov
full_name: Karasik, Yakov
last_name: Karasik
citation:
ama: Horesh T, Karasik Y. Equidistribution of primitive lattices in ℝn. Quarterly
Journal of Mathematics. 2023;74(4):1253-1294. doi:10.1093/qmath/haad008
apa: Horesh, T., & Karasik, Y. (2023). Equidistribution of primitive lattices
in ℝn. Quarterly Journal of Mathematics. Oxford University Press. https://doi.org/10.1093/qmath/haad008
chicago: Horesh, Tal, and Yakov Karasik. “Equidistribution of Primitive Lattices
in ℝn.” Quarterly Journal of Mathematics. Oxford University Press, 2023.
https://doi.org/10.1093/qmath/haad008.
ieee: T. Horesh and Y. Karasik, “Equidistribution of primitive lattices in ℝn,”
Quarterly Journal of Mathematics, vol. 74, no. 4. Oxford University Press,
pp. 1253–1294, 2023.
ista: Horesh T, Karasik Y. 2023. Equidistribution of primitive lattices in ℝn. Quarterly
Journal of Mathematics. 74(4), 1253–1294.
mla: Horesh, Tal, and Yakov Karasik. “Equidistribution of Primitive Lattices in
ℝn.” Quarterly Journal of Mathematics, vol. 74, no. 4, Oxford University
Press, 2023, pp. 1253–94, doi:10.1093/qmath/haad008.
short: T. Horesh, Y. Karasik, Quarterly Journal of Mathematics 74 (2023) 1253–1294.
date_created: 2023-12-31T23:01:03Z
date_published: 2023-12-01T00:00:00Z
date_updated: 2024-01-02T07:39:55Z
day: '01'
ddc:
- '510'
department:
- _id: TiBr
doi: 10.1093/qmath/haad008
external_id:
arxiv:
- '2012.04508'
file:
- access_level: open_access
checksum: bf29baa9eae8500f3374dbcb80712687
content_type: application/pdf
creator: dernst
date_created: 2024-01-02T07:37:09Z
date_updated: 2024-01-02T07:37:09Z
file_id: '14720'
file_name: 2023_QuarterlyJourMath_Horesh.pdf
file_size: 724748
relation: main_file
success: 1
file_date_updated: 2024-01-02T07:37:09Z
has_accepted_license: '1'
intvolume: ' 74'
issue: '4'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: 1253-1294
project:
- _id: 26A8D266-B435-11E9-9278-68D0E5697425
grant_number: EP-P026710-2
name: Between rational and integral points
publication: Quarterly Journal of Mathematics
publication_identifier:
eissn:
- 1464-3847
issn:
- 0033-5606
publication_status: published
publisher: Oxford University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Equidistribution of primitive lattices in ℝn
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 74
year: '2023'
...
---
_id: '14718'
abstract:
- lang: eng
text: 'Binary decision diagrams (BDDs) are one of the fundamental data structures
in formal methods and computer science in general. However, the performance of
BDD-based algorithms greatly depends on memory latency due to the reliance on
large hash tables and thus, by extension, on the speed of random memory access.
This hinders the full utilisation of resources available on modern CPUs, since
the absolute memory latency has not improved significantly for at least a decade.
In this paper, we explore several implementation techniques that improve the performance
of BDD manipulation either through enhanced memory locality or by partially eliminating
random memory access. On a benchmark suite of 600+ BDDs derived from real-world
applications, we demonstrate runtime that is comparable or better than parallelising
the same operations on eight CPU cores. '
acknowledgement: "This work was supported by the European Union’s Horizon 2020 research
and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 101034413
and the\r\n“VAMOS” grant ERC-2020-AdG 101020093."
article_processing_charge: No
author:
- first_name: Samuel
full_name: Pastva, Samuel
id: 07c5ea74-f61c-11ec-a664-aa7c5d957b2b
last_name: Pastva
orcid: 0000-0003-1993-0331
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
citation:
ama: 'Pastva S, Henzinger TA. Binary decision diagrams on modern hardware. In: Proceedings
of the 23rd Conference on Formal Methods in Computer-Aided Design. TU Vienna
Academic Press; 2023:122-131. doi:10.34727/2023/isbn.978-3-85448-060-0_20'
apa: 'Pastva, S., & Henzinger, T. A. (2023). Binary decision diagrams on modern
hardware. In Proceedings of the 23rd Conference on Formal Methods in Computer-Aided
Design (pp. 122–131). Ames, IA, United States: TU Vienna Academic Press. https://doi.org/10.34727/2023/isbn.978-3-85448-060-0_20'
chicago: Pastva, Samuel, and Thomas A Henzinger. “Binary Decision Diagrams on Modern
Hardware.” In Proceedings of the 23rd Conference on Formal Methods in Computer-Aided
Design, 122–31. TU Vienna Academic Press, 2023. https://doi.org/10.34727/2023/isbn.978-3-85448-060-0_20.
ieee: S. Pastva and T. A. Henzinger, “Binary decision diagrams on modern hardware,”
in Proceedings of the 23rd Conference on Formal Methods in Computer-Aided Design,
Ames, IA, United States, 2023, pp. 122–131.
ista: 'Pastva S, Henzinger TA. 2023. Binary decision diagrams on modern hardware.
Proceedings of the 23rd Conference on Formal Methods in Computer-Aided Design.
FMCAD: Conference on Formal Methods in Computer-aided design, 122–131.'
mla: Pastva, Samuel, and Thomas A. Henzinger. “Binary Decision Diagrams on Modern
Hardware.” Proceedings of the 23rd Conference on Formal Methods in Computer-Aided
Design, TU Vienna Academic Press, 2023, pp. 122–31, doi:10.34727/2023/isbn.978-3-85448-060-0_20.
short: S. Pastva, T.A. Henzinger, in:, Proceedings of the 23rd Conference on Formal
Methods in Computer-Aided Design, TU Vienna Academic Press, 2023, pp. 122–131.
conference:
end_date: 2023-10-27
location: Ames, IA, United States
name: 'FMCAD: Conference on Formal Methods in Computer-aided design'
start_date: 2023-10-25
date_created: 2023-12-31T23:01:03Z
date_published: 2023-10-01T00:00:00Z
date_updated: 2024-01-02T08:16:28Z
day: '01'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.34727/2023/isbn.978-3-85448-060-0_20
ec_funded: 1
file:
- access_level: open_access
checksum: 818d6e13dd508f3a04f0941081022e5d
content_type: application/pdf
creator: dernst
date_created: 2024-01-02T08:14:23Z
date_updated: 2024-01-02T08:14:23Z
file_id: '14721'
file_name: 2023_FMCAD_Pastva.pdf
file_size: 524321
relation: main_file
success: 1
file_date_updated: 2024-01-02T08:14:23Z
has_accepted_license: '1'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
page: 122-131
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
publication: Proceedings of the 23rd Conference on Formal Methods in Computer-Aided
Design
publication_identifier:
isbn:
- '9783854480600'
publication_status: published
publisher: TU Vienna Academic Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Binary decision diagrams on modern hardware
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...
---
_id: '14726'
abstract:
- lang: eng
text: Autocrine signaling pathways regulated by RAPID ALKALINIZATION FACTORs (RALFs)
control cell wall integrity during pollen tube germination and growth in Arabidopsis
(Arabidopsis thaliana). To investigate the role of pollen-specific RALFs in another
plant species, we combined gene expression data with phylogenetic and biochemical
studies to identify candidate orthologs in maize (Zea mays). We show that Clade
IB ZmRALF2/3 mutations, but not Clade III ZmRALF1/5 mutations, cause cell wall
instability in the sub-apical region of the growing pollen tube. ZmRALF2/3 are
mainly located in the cell wall and are partially able to complement the pollen
germination defect of their Arabidopsis orthologs AtRALF4/19. Mutations in ZmRALF2/3
compromise pectin distribution patterns leading to altered cell wall organization
and thickness culminating in pollen tube burst. Clade IB, but not Clade III ZmRALFs,
strongly interact as ligands with the pollen-specific Catharanthus roseus RLK1-like
(CrRLK1L) receptor kinases Zea mays FERONIA-like (ZmFERL) 4/7/9, LORELEI-like
glycosylphosphatidylinositol-anchor (LLG) proteins Zea mays LLG 1 and 2 (ZmLLG1/2)
and Zea mays pollen extension-like (PEX) cell wall proteins ZmPEX2/4. Notably,
ZmFERL4 outcompetes ZmLLG2 and ZmPEX2 outcompetes ZmFERL4 for ZmRALF2 binding.
Based on these data, we suggest that Clade IB RALFs act in a dual role as cell
wall components and extracellular sensors to regulate cell wall integrity and
thickness during pollen tube growth in maize and probably other plants.
article_number: koad324
article_processing_charge: No
article_type: original
author:
- first_name: Liang-Zi
full_name: Zhou, Liang-Zi
last_name: Zhou
- first_name: Lele
full_name: Wang, Lele
last_name: Wang
- first_name: Xia
full_name: Chen, Xia
last_name: Chen
- first_name: Zengxiang
full_name: Ge, Zengxiang
id: f43371a3-09ff-11eb-8013-bd0c6a2f6de8
last_name: Ge
orcid: 0000-0001-9381-3577
- first_name: Julia
full_name: Mergner, Julia
last_name: Mergner
- first_name: Xingli
full_name: Li, Xingli
last_name: Li
- first_name: Bernhard
full_name: Küster, Bernhard
last_name: Küster
- first_name: Gernot
full_name: Längst, Gernot
last_name: Längst
- first_name: Li-Jia
full_name: Qu, Li-Jia
last_name: Qu
- first_name: Thomas
full_name: Dresselhaus, Thomas
last_name: Dresselhaus
citation:
ama: Zhou L-Z, Wang L, Chen X, et al. The RALF signaling pathway regulates cell
wall integrity during pollen tube growth in maize. The Plant Cell. 2023.
doi:10.1093/plcell/koad324
apa: Zhou, L.-Z., Wang, L., Chen, X., Ge, Z., Mergner, J., Li, X., … Dresselhaus,
T. (2023). The RALF signaling pathway regulates cell wall integrity during pollen
tube growth in maize. The Plant Cell. Oxford University Press. https://doi.org/10.1093/plcell/koad324
chicago: Zhou, Liang-Zi, Lele Wang, Xia Chen, Zengxiang Ge, Julia Mergner, Xingli
Li, Bernhard Küster, Gernot Längst, Li-Jia Qu, and Thomas Dresselhaus. “The RALF
Signaling Pathway Regulates Cell Wall Integrity during Pollen Tube Growth in Maize.”
The Plant Cell. Oxford University Press, 2023. https://doi.org/10.1093/plcell/koad324.
ieee: L.-Z. Zhou et al., “The RALF signaling pathway regulates cell wall
integrity during pollen tube growth in maize,” The Plant Cell. Oxford University
Press, 2023.
ista: Zhou L-Z, Wang L, Chen X, Ge Z, Mergner J, Li X, Küster B, Längst G, Qu L-J,
Dresselhaus T. 2023. The RALF signaling pathway regulates cell wall integrity
during pollen tube growth in maize. The Plant Cell., koad324.
mla: Zhou, Liang-Zi, et al. “The RALF Signaling Pathway Regulates Cell Wall Integrity
during Pollen Tube Growth in Maize.” The Plant Cell, koad324, Oxford University
Press, 2023, doi:10.1093/plcell/koad324.
short: L.-Z. Zhou, L. Wang, X. Chen, Z. Ge, J. Mergner, X. Li, B. Küster, G. Längst,
L.-J. Qu, T. Dresselhaus, The Plant Cell (2023).
date_created: 2024-01-02T11:19:37Z
date_published: 2023-12-23T00:00:00Z
date_updated: 2024-01-03T12:43:41Z
day: '23'
ddc:
- '580'
doi: 10.1093/plcell/koad324
extern: '1'
has_accepted_license: '1'
keyword:
- Cell Biology
- Plant Science
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1093/plcell/koad324
month: '12'
oa: 1
oa_version: Published Version
publication: The Plant Cell
publication_identifier:
eissn:
- 1532-298X
issn:
- 1040-4651
publication_status: epub_ahead
publisher: Oxford University Press
quality_controlled: '1'
status: public
title: The RALF signaling pathway regulates cell wall integrity during pollen tube
growth in maize
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
(CC BY-NC-ND 4.0)
short: CC BY-NC-ND (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...
---
_id: '14732'
abstract:
- lang: eng
text: 'Fragmented landscapes pose a significant threat to the persistence of species
as they are highly susceptible to heightened risk of extinction due to the combined
effects of genetic and demographic factors such as genetic drift and demographic
stochasticity. This paper explores the intricate interplay between genetic load
and extinction risk within metapopulations with a focus on understanding the impact
of eco-evolutionary feedback mechanisms. We distinguish between two models of
selection: soft selection, characterised by subpopulations maintaining carrying
capacity despite load, and hard selection, where load can significantly affect
population size. Within the soft selection framework, we investigate the impact
of gene flow on genetic load at a single locus, while also considering the effect
of selection strength and dominance coefficient. We subsequently build on this
to examine how gene flow influences both population size and load under hard selection
as well as identify critical thresholds for metapopulation persistence. Our analysis
employs the diffusion, semi-deterministic and effective migration approximations.
Our findings reveal that under soft selection, even modest levels of migration
can significantly alleviate the burden of load. In sharp contrast, with hard selection,
a much higher degree of gene flow is required to mitigate load and prevent the
collapse of the metapopulation. Overall, this study sheds light into the crucial
role migration plays in shaping the dynamics of genetic load and extinction risk
in fragmented landscapes, offering valuable insights for conservation strategies
and the preservation of diversity in a changing world.'
article_processing_charge: No
author:
- first_name: Oluwafunmilola O
full_name: Olusanya, Oluwafunmilola O
id: 41AD96DC-F248-11E8-B48F-1D18A9856A87
last_name: Olusanya
orcid: 0000-0003-1971-8314
- first_name: Kseniia
full_name: Khudiakova, Kseniia
id: 4E6DC800-AE37-11E9-AC72-31CAE5697425
last_name: Khudiakova
orcid: 0000-0002-6246-1465
- first_name: Himani
full_name: Sachdeva, Himani
id: 42377A0A-F248-11E8-B48F-1D18A9856A87
last_name: Sachdeva
citation:
ama: Olusanya OO, Khudiakova K, Sachdeva H. Genetic load, eco-evolutionary feedback
and extinction in a metapopulation. bioRxiv. doi:10.1101/2023.12.02.569702
apa: Olusanya, O. O., Khudiakova, K., & Sachdeva, H. (n.d.). Genetic load, eco-evolutionary
feedback and extinction in a metapopulation. bioRxiv. https://doi.org/10.1101/2023.12.02.569702
chicago: Olusanya, Oluwafunmilola O, Kseniia Khudiakova, and Himani Sachdeva. “Genetic
Load, Eco-Evolutionary Feedback and Extinction in a Metapopulation.” BioRxiv,
n.d. https://doi.org/10.1101/2023.12.02.569702.
ieee: O. O. Olusanya, K. Khudiakova, and H. Sachdeva, “Genetic load, eco-evolutionary
feedback and extinction in a metapopulation,” bioRxiv. .
ista: Olusanya OO, Khudiakova K, Sachdeva H. Genetic load, eco-evolutionary feedback
and extinction in a metapopulation. bioRxiv, 10.1101/2023.12.02.569702.
mla: Olusanya, Oluwafunmilola O., et al. “Genetic Load, Eco-Evolutionary Feedback
and Extinction in a Metapopulation.” BioRxiv, doi:10.1101/2023.12.02.569702.
short: O.O. Olusanya, K. Khudiakova, H. Sachdeva, BioRxiv (n.d.).
date_created: 2024-01-04T09:35:54Z
date_published: 2023-12-04T00:00:00Z
date_updated: 2025-05-26T09:05:10Z
day: '04'
department:
- _id: NiBa
- _id: JaMa
doi: 10.1101/2023.12.02.569702
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.biorxiv.org/content/10.1101/2023.12.02.569702v1
month: '12'
oa: 1
oa_version: Preprint
project:
- _id: c08d3278-5a5b-11eb-8a69-fdb09b55f4b8
grant_number: P32896
name: Causes and consequences of population fragmentation
- _id: 34d33d68-11ca-11ed-8bc3-ec13763c0ca8
grant_number: '26293'
name: The impact of deleterious mutations on small populations
- _id: 34c872fe-11ca-11ed-8bc3-8534b82131e6
grant_number: '26380'
name: Polygenic Adaptation in a Metapopulation
publication: bioRxiv
publication_status: submitted
related_material:
record:
- id: '14711'
relation: dissertation_contains
status: public
status: public
title: Genetic load, eco-evolutionary feedback and extinction in a metapopulation
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
(CC BY-NC-ND 4.0)
short: CC BY-NC-ND (4.0)
type: preprint
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2023'
...
---
_id: '14733'
abstract:
- lang: eng
text: Redox flow batteries (RFBs) rely on the development of cheap, highly soluble,
and high-energy-density electrolytes. Several candidate quinones have already
been investigated in the literature as two-electron anolytes or catholytes, benefiting
from fast kinetics, high tunability, and low cost. Here, an investigation of nitrogen-rich
fused heteroaromatic quinones was carried out to explore avenues for electrolyte
development. These quinones were synthesized and screened by using electrochemical
techniques. The most promising candidate, 4,8-dioxo-4,8-dihydrobenzo[1,2-d:4,5-d′]bis([1,2,3]triazole)-1,5-diide
(−0.68 V(SHE)), was tested in both an asymmetric and symmetric full-cell setup
resulting in capacity fade rates of 0.35% per cycle and 0.0124% per cycle, respectively.
In situ ultraviolet-visible spectroscopy (UV–Vis), nuclear magnetic resonance
(NMR), and electron paramagnetic resonance (EPR) spectroscopies were used to investigate
the electrochemical stability of the charged species during operation. UV–Vis
spectroscopy, supported by density functional theory (DFT) modeling, reaffirmed
that the two-step charging mechanism observed during battery operation consisted
of two, single-electron transfers. The radical concentration during battery operation
and the degree of delocalization of the unpaired electron were quantified with
NMR and EPR spectroscopy.
article_processing_charge: Yes (in subscription journal)
article_type: original
author:
- first_name: Rajesh B
full_name: Jethwa, Rajesh B
id: 4cc538d5-803f-11ed-ab7e-8139573aad8f
last_name: Jethwa
orcid: 0000-0002-0404-4356
- first_name: Dominic
full_name: Hey, Dominic
last_name: Hey
- first_name: Rachel N.
full_name: Kerber, Rachel N.
last_name: Kerber
- first_name: Andrew D.
full_name: Bond, Andrew D.
last_name: Bond
- first_name: Dominic S.
full_name: Wright, Dominic S.
last_name: Wright
- first_name: Clare P.
full_name: Grey, Clare P.
last_name: Grey
citation:
ama: Jethwa RB, Hey D, Kerber RN, Bond AD, Wright DS, Grey CP. Exploring the landscape
of heterocyclic quinones for redox flow batteries. ACS Applied Energy Materials.
2023. doi:10.1021/acsaem.3c02223
apa: Jethwa, R. B., Hey, D., Kerber, R. N., Bond, A. D., Wright, D. S., & Grey,
C. P. (2023). Exploring the landscape of heterocyclic quinones for redox flow
batteries. ACS Applied Energy Materials. American Chemical Society. https://doi.org/10.1021/acsaem.3c02223
chicago: Jethwa, Rajesh B, Dominic Hey, Rachel N. Kerber, Andrew D. Bond, Dominic
S. Wright, and Clare P. Grey. “Exploring the Landscape of Heterocyclic Quinones
for Redox Flow Batteries.” ACS Applied Energy Materials. American Chemical
Society, 2023. https://doi.org/10.1021/acsaem.3c02223.
ieee: R. B. Jethwa, D. Hey, R. N. Kerber, A. D. Bond, D. S. Wright, and C. P. Grey,
“Exploring the landscape of heterocyclic quinones for redox flow batteries,” ACS
Applied Energy Materials. American Chemical Society, 2023.
ista: Jethwa RB, Hey D, Kerber RN, Bond AD, Wright DS, Grey CP. 2023. Exploring
the landscape of heterocyclic quinones for redox flow batteries. ACS Applied Energy
Materials.
mla: Jethwa, Rajesh B., et al. “Exploring the Landscape of Heterocyclic Quinones
for Redox Flow Batteries.” ACS Applied Energy Materials, American Chemical
Society, 2023, doi:10.1021/acsaem.3c02223.
short: R.B. Jethwa, D. Hey, R.N. Kerber, A.D. Bond, D.S. Wright, C.P. Grey, ACS
Applied Energy Materials (2023).
date_created: 2024-01-05T09:20:48Z
date_published: 2023-12-28T00:00:00Z
date_updated: 2024-01-08T09:03:01Z
day: '28'
ddc:
- '540'
department:
- _id: StFr
doi: 10.1021/acsaem.3c02223
ec_funded: 1
has_accepted_license: '1'
keyword:
- Electrical and Electronic Engineering
- Materials Chemistry
- Electrochemistry
- Energy Engineering and Power Technology
- Chemical Engineering (miscellaneous)
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1021/acsaem.3c02223
month: '12'
oa: 1
oa_version: Published Version
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: ACS Applied Energy Materials
publication_identifier:
eissn:
- 2574-0962
publication_status: epub_ahead
publisher: American Chemical Society
quality_controlled: '1'
status: public
title: Exploring the landscape of heterocyclic quinones for redox flow batteries
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...
---
_id: '14735'
abstract:
- lang: eng
text: "Scaling blockchain protocols to perform on par with the expected needs of
Web3.0 has been proven to be a challenging task with almost a decade of research.
In the forefront of the current solution is the idea of separating the execution
of the updates encoded in a block from the ordering of blocks. In order to achieve
this, a new class of protocols called rollups has emerged. Rollups have as input
a total ordering of valid and invalid transactions and as output a new valid state-transition.\r\nIf
we study rollups from a distributed computing perspective, we uncover that rollups
take as input the output of a Byzantine Atomic Broadcast (BAB) protocol and convert
it to a State Machine Replication (SMR) protocol. BAB and SMR, however, are considered
equivalent as far as distributed computing is concerned and a solution to one
can easily be retrofitted to solve the other simply by adding/removing an execution
step before the validation of the input.\r\nThis “easy” step of retrofitting an
atomic broadcast solution to implement an SMR has, however, been overlooked in
practice. In this paper, we formalize the problem and show that after BAB is solved,
traditional impossibility results for consensus no longer apply towards an SMR.
Leveraging this we propose a distributed execution protocol that allows reduced
execution and storage cost per executor (O(log2n/n)) without relaxing the network
assumptions of the underlying BAB protocol and providing censorship-resistance.
Finally, we propose efficient non-interactive light client constructions that
leverage our efficient execution protocols and do not require any synchrony assumptions
or expensive ZK-proofs."
acknowledgement: 'Eleftherios Kokoris-Kogias is partially supported by Austrian Science
Fund (FWF) grant No: F8512-N.'
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Christos
full_name: Stefo, Christos
id: a20e8902-32b0-11ee-9fa8-b23fa638b793
last_name: Stefo
- first_name: Zhuolun
full_name: Xiang, Zhuolun
last_name: Xiang
- first_name: Eleftherios
full_name: Kokoris Kogias, Eleftherios
id: f5983044-d7ef-11ea-ac6d-fd1430a26d30
last_name: Kokoris Kogias
citation:
ama: 'Stefo C, Xiang Z, Kokoris Kogias E. Executing and proving over dirty ledgers.
In: 27th International Conference on Financial Cryptography and Data Security.
Vol 13950. Springer Nature; 2023:3-20. doi:10.1007/978-3-031-47754-6_1'
apa: 'Stefo, C., Xiang, Z., & Kokoris Kogias, E. (2023). Executing and proving
over dirty ledgers. In 27th International Conference on Financial Cryptography
and Data Security (Vol. 13950, pp. 3–20). Bol, Brac, Croatia: Springer Nature.
https://doi.org/10.1007/978-3-031-47754-6_1'
chicago: Stefo, Christos, Zhuolun Xiang, and Eleftherios Kokoris Kogias. “Executing
and Proving over Dirty Ledgers.” In 27th International Conference on Financial
Cryptography and Data Security, 13950:3–20. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-47754-6_1.
ieee: C. Stefo, Z. Xiang, and E. Kokoris Kogias, “Executing and proving over dirty
ledgers,” in 27th International Conference on Financial Cryptography and Data
Security, Bol, Brac, Croatia, 2023, vol. 13950, pp. 3–20.
ista: 'Stefo C, Xiang Z, Kokoris Kogias E. 2023. Executing and proving over dirty
ledgers. 27th International Conference on Financial Cryptography and Data Security.
FC: Financial Cryptography and Data Security, LNCS, vol. 13950, 3–20.'
mla: Stefo, Christos, et al. “Executing and Proving over Dirty Ledgers.” 27th
International Conference on Financial Cryptography and Data Security, vol.
13950, Springer Nature, 2023, pp. 3–20, doi:10.1007/978-3-031-47754-6_1.
short: C. Stefo, Z. Xiang, E. Kokoris Kogias, in:, 27th International Conference
on Financial Cryptography and Data Security, Springer Nature, 2023, pp. 3–20.
conference:
end_date: 2023-05-05
location: Bol, Brac, Croatia
name: 'FC: Financial Cryptography and Data Security'
start_date: 2023-05-01
date_created: 2024-01-08T09:17:38Z
date_published: 2023-12-01T00:00:00Z
date_updated: 2024-01-08T09:28:14Z
day: '01'
department:
- _id: ElKo
- _id: GradSch
doi: 10.1007/978-3-031-47754-6_1
intvolume: ' 13950'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2022/1554
month: '12'
oa: 1
oa_version: Preprint
page: 3-20
project:
- _id: 34a4ce89-11ca-11ed-8bc3-8cc37fb6e11f
grant_number: F8512
name: Secure Network and Hardware for Efficient Blockchains
publication: 27th International Conference on Financial Cryptography and Data Security
publication_identifier:
eisbn:
- '9783031477546'
eissn:
- 0302-9743
isbn:
- '9783031477539'
issn:
- 1611-3349
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Executing and proving over dirty ledgers
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13950
year: '2023'
...
---
_id: '14737'
abstract:
- lang: eng
text: 'John’s fundamental theorem characterizing the largest volume ellipsoid contained
in a convex body $K$ in $\mathbb{R}^{d}$ has seen several generalizations and
extensions. One direction, initiated by V. Milman is to replace ellipsoids by
positions (affine images) of another body $L$. Another, more recent direction
is to consider logarithmically concave functions on $\mathbb{R}^{d}$ instead of
convex bodies: we designate some special, radially symmetric log-concave function
$g$ as the analogue of the Euclidean ball, and want to find its largest integral
position under the constraint that it is pointwise below some given log-concave
function $f$. We follow both directions simultaneously: we consider the functional
question, and allow essentially any meaningful function to play the role of $g$
above. Our general theorems jointly extend known results in both directions. The
dual problem in the setting of convex bodies asks for the smallest volume ellipsoid,
called Löwner’s ellipsoid, containing $K$. We consider the analogous problem for
functions: we characterize the solutions of the optimization problem of finding
a smallest integral position of some log-concave function $g$ under the constraint
that it is pointwise above $f$. It turns out that in the functional setting, the
relationship between the John and the Löwner problems is more intricate than it
is in the setting of convex bodies.'
acknowledgement: "We thank Alexander Litvak for the many discussions on Theorem 1.1.
Igor Tsiutsiurupa participated in the early stage of this project. To our deep regret,
Igor chose another road for his life and stopped working with us.\r\nThis work was
supported by the János Bolyai Scholarship of the Hungarian Academy of Sciences [to
M.N.]; the National Research, Development, and Innovation Fund (NRDI) [K119670 and
K131529 to M.N.]; and the ÚNKP-22-5 New National Excellence Program of the Ministry
for Innovation and Technology from the source of the NRDI [to M.N.]."
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Grigory
full_name: Ivanov, Grigory
id: 87744F66-5C6F-11EA-AFE0-D16B3DDC885E
last_name: Ivanov
- first_name: Márton
full_name: Naszódi, Márton
last_name: Naszódi
citation:
ama: Ivanov G, Naszódi M. Functional John and Löwner conditions for pairs of log-concave
functions. International Mathematics Research Notices. 2023;2023(23):20613-20669.
doi:10.1093/imrn/rnad210
apa: Ivanov, G., & Naszódi, M. (2023). Functional John and Löwner conditions
for pairs of log-concave functions. International Mathematics Research Notices.
Oxford University Press. https://doi.org/10.1093/imrn/rnad210
chicago: Ivanov, Grigory, and Márton Naszódi. “Functional John and Löwner Conditions
for Pairs of Log-Concave Functions.” International Mathematics Research Notices.
Oxford University Press, 2023. https://doi.org/10.1093/imrn/rnad210.
ieee: G. Ivanov and M. Naszódi, “Functional John and Löwner conditions for pairs
of log-concave functions,” International Mathematics Research Notices,
vol. 2023, no. 23. Oxford University Press, pp. 20613–20669, 2023.
ista: Ivanov G, Naszódi M. 2023. Functional John and Löwner conditions for pairs
of log-concave functions. International Mathematics Research Notices. 2023(23),
20613–20669.
mla: Ivanov, Grigory, and Márton Naszódi. “Functional John and Löwner Conditions
for Pairs of Log-Concave Functions.” International Mathematics Research Notices,
vol. 2023, no. 23, Oxford University Press, 2023, pp. 20613–69, doi:10.1093/imrn/rnad210.
short: G. Ivanov, M. Naszódi, International Mathematics Research Notices 2023 (2023)
20613–20669.
date_created: 2024-01-08T09:48:56Z
date_published: 2023-12-01T00:00:00Z
date_updated: 2024-01-08T09:57:25Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.1093/imrn/rnad210
external_id:
arxiv:
- '2212.11781'
file:
- access_level: open_access
checksum: 353666cea80633beb0f1ffd342dff6d4
content_type: application/pdf
creator: dernst
date_created: 2024-01-08T09:53:09Z
date_updated: 2024-01-08T09:53:09Z
file_id: '14738'
file_name: 2023_IMRN_Ivanov.pdf
file_size: 815777
relation: main_file
success: 1
file_date_updated: 2024-01-08T09:53:09Z
has_accepted_license: '1'
intvolume: ' 2023'
issue: '23'
keyword:
- General Mathematics
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: 20613-20669
publication: International Mathematics Research Notices
publication_identifier:
eissn:
- 1687-0247
issn:
- 1073-7928
publication_status: published
publisher: Oxford University Press
quality_controlled: '1'
status: public
title: Functional John and Löwner conditions for pairs of log-concave functions
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
(CC BY-NC-ND 4.0)
short: CC BY-NC-ND (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2023
year: '2023'
...
---
_id: '14739'
abstract:
- lang: eng
text: Attempts to incorporate topological information in supervised learning tasks
have resulted in the creation of several techniques for vectorizing persistent
homology barcodes. In this paper, we study thirteen such methods. Besides describing
an organizational framework for these methods, we comprehensively benchmark them
against three well-known classification tasks. Surprisingly, we discover that
the best-performing method is a simple vectorization, which consists only of a
few elementary summary statistics. Finally, we provide a convenient web application
which has been designed to facilitate exploration and experimentation with various
vectorization methods.
acknowledgement: "The work of Maria-Jose Jimenez, Eduardo Paluzo-Hidalgo and Manuel
Soriano-Trigueros was supported in part by the Spanish grant Ministerio de Ciencia
e Innovacion under Grants TED2021-129438B-I00 and PID2019-107339GB-I00, and in part
by REXASI-PRO H-EU project, call HORIZON-CL4-2021-HUMAN-01-01 under Grant 101070028.
The work of\r\nMaria-Jose Jimenez was supported by a grant of Convocatoria de la
Universidad de Sevilla para la recualificacion del sistema universitario español,
2021-23, funded by the European Union, NextGenerationEU. The work of Vidit Nanda
was supported in part by EPSRC under Grant EP/R018472/1 and in part by US AFOSR
under Grant FA9550-22-1-0462. \r\nWe are grateful to the team of GUDHI and TEASPOON
developers, for their work and their support. We are also grateful to Streamlit
for providing extra resources to deploy the web app\r\nonline on Streamlit community
cloud. We thank the anonymous referees for their helpful suggestions."
article_processing_charge: Yes (in subscription journal)
article_type: original
author:
- first_name: Dashti
full_name: Ali, Dashti
last_name: Ali
- first_name: Aras
full_name: Asaad, Aras
last_name: Asaad
- first_name: Maria-Jose
full_name: Jimenez, Maria-Jose
last_name: Jimenez
- first_name: Vidit
full_name: Nanda, Vidit
last_name: Nanda
- first_name: Eduardo
full_name: Paluzo-Hidalgo, Eduardo
last_name: Paluzo-Hidalgo
- first_name: Manuel
full_name: Soriano Trigueros, Manuel
id: 15ebd7cf-15bf-11ee-aebd-bb4bb5121ea8
last_name: Soriano Trigueros
orcid: 0000-0003-2449-1433
citation:
ama: Ali D, Asaad A, Jimenez M-J, Nanda V, Paluzo-Hidalgo E, Soriano Trigueros M.
A survey of vectorization methods in topological data analysis. IEEE Transactions
on Pattern Analysis and Machine Intelligence. 2023;45(12):14069-14080. doi:10.1109/tpami.2023.3308391
apa: Ali, D., Asaad, A., Jimenez, M.-J., Nanda, V., Paluzo-Hidalgo, E., & Soriano
Trigueros, M. (2023). A survey of vectorization methods in topological data analysis.
IEEE Transactions on Pattern Analysis and Machine Intelligence. IEEE. https://doi.org/10.1109/tpami.2023.3308391
chicago: Ali, Dashti, Aras Asaad, Maria-Jose Jimenez, Vidit Nanda, Eduardo Paluzo-Hidalgo,
and Manuel Soriano Trigueros. “A Survey of Vectorization Methods in Topological
Data Analysis.” IEEE Transactions on Pattern Analysis and Machine Intelligence.
IEEE, 2023. https://doi.org/10.1109/tpami.2023.3308391.
ieee: D. Ali, A. Asaad, M.-J. Jimenez, V. Nanda, E. Paluzo-Hidalgo, and M. Soriano
Trigueros, “A survey of vectorization methods in topological data analysis,” IEEE
Transactions on Pattern Analysis and Machine Intelligence, vol. 45, no. 12.
IEEE, pp. 14069–14080, 2023.
ista: Ali D, Asaad A, Jimenez M-J, Nanda V, Paluzo-Hidalgo E, Soriano Trigueros
M. 2023. A survey of vectorization methods in topological data analysis. IEEE
Transactions on Pattern Analysis and Machine Intelligence. 45(12), 14069–14080.
mla: Ali, Dashti, et al. “A Survey of Vectorization Methods in Topological Data
Analysis.” IEEE Transactions on Pattern Analysis and Machine Intelligence,
vol. 45, no. 12, IEEE, 2023, pp. 14069–80, doi:10.1109/tpami.2023.3308391.
short: D. Ali, A. Asaad, M.-J. Jimenez, V. Nanda, E. Paluzo-Hidalgo, M. Soriano
Trigueros, IEEE Transactions on Pattern Analysis and Machine Intelligence 45 (2023)
14069–14080.
date_created: 2024-01-08T09:59:46Z
date_published: 2023-12-01T00:00:00Z
date_updated: 2024-01-08T10:11:46Z
day: '01'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.1109/tpami.2023.3308391
file:
- access_level: open_access
checksum: 465c28ef0b151b4b1fb47977ed5581ab
content_type: application/pdf
creator: dernst
date_created: 2024-01-08T10:09:14Z
date_updated: 2024-01-08T10:09:14Z
file_id: '14740'
file_name: 2023_IEEEToP_Ali.pdf
file_size: 2370988
relation: main_file
success: 1
file_date_updated: 2024-01-08T10:09:14Z
has_accepted_license: '1'
intvolume: ' 45'
issue: '12'
keyword:
- Applied Mathematics
- Artificial Intelligence
- Computational Theory and Mathematics
- Computer Vision and Pattern Recognition
- Software
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: 14069-14080
publication: IEEE Transactions on Pattern Analysis and Machine Intelligence
publication_identifier:
eissn:
- 1939-3539
issn:
- 0162-8828
publication_status: published
publisher: IEEE
quality_controlled: '1'
status: public
title: A survey of vectorization methods in topological data analysis
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 45
year: '2023'
...
---
_id: '14742'
abstract:
- lang: eng
text: "Chromosomal rearrangements (CRs) have been known since almost the beginning
of genetics.\r\nWhile an important role for CRs in speciation has been suggested,
evidence primarily stems\r\nfrom theoretical and empirical studies focusing on
the microevolutionary level (i.e., on taxon\r\npairs where speciation is often
incomplete). Although the role of CRs in eukaryotic speciation at\r\na macroevolutionary
level has been supported by associations between species diversity and\r\nrates
of evolution of CRs across phylogenies, these findings are limited to a restricted
range of\r\nCRs and taxa. Now that more broadly applicable and precise CR detection
approaches have\r\nbecome available, we address the challenges in filling some
of the conceptual and empirical\r\ngaps between micro- and macroevolutionary studies
on the role of CRs in speciation. We\r\nsynthesize what is known about the macroevolutionary
impact of CRs and suggest new research avenues to overcome the pitfalls of previous
studies to gain a more comprehensive understanding of the evolutionary significance
of CRs in speciation across the tree of life."
acknowledgement: "K.L. was funded by a Swiss National Science Foundation Eccellenza
project: The evolution of strong reproductive barriers towards the completion of
speciation (PCEFP3_202869). R.F.\r\nwas funded by an FCT CEEC (Fundação para a Ciênca
e a Tecnologia, Concurso Estímulo ao\r\nEmprego Científico) contract (2020.00275.
CEECIND) and by an FCT research project\r\n(PTDC/BIA-EVL/1614/2021). M.R. was funded
by the Swedish Research Council Vetenskapsrådet (grant number 2021-05243). A.M.W.
was partly funded by the Norwegian Research Council RCN. We thank Luis Silva for
his help preparing Figure 1. We are grateful to Maren Wellenreuther, Daniel Bolnick,
and two anonymous reviewers for their constructive feedback on an earlier version
of this paper."
article_number: a041447
article_processing_charge: No
article_type: original
author:
- first_name: Kay
full_name: Lucek, Kay
last_name: Lucek
- first_name: Mabel D.
full_name: Giménez, Mabel D.
last_name: Giménez
- first_name: Mathieu
full_name: Joron, Mathieu
last_name: Joron
- first_name: Marina
full_name: Rafajlović, Marina
last_name: Rafajlović
- first_name: Jeremy B.
full_name: Searle, Jeremy B.
last_name: Searle
- first_name: Nora
full_name: Walden, Nora
last_name: Walden
- first_name: Anja M
full_name: Westram, Anja M
id: 3C147470-F248-11E8-B48F-1D18A9856A87
last_name: Westram
orcid: 0000-0003-1050-4969
- first_name: Rui
full_name: Faria, Rui
last_name: Faria
citation:
ama: 'Lucek K, Giménez MD, Joron M, et al. The impact of chromosomal rearrangements
in speciation: From micro- to macroevolution. Cold Spring Harbor Perspectives
in Biology. 2023;15(11). doi:10.1101/cshperspect.a041447'
apa: 'Lucek, K., Giménez, M. D., Joron, M., Rafajlović, M., Searle, J. B., Walden,
N., … Faria, R. (2023). The impact of chromosomal rearrangements in speciation:
From micro- to macroevolution. Cold Spring Harbor Perspectives in Biology.
Cold Spring Harbor Laboratory. https://doi.org/10.1101/cshperspect.a041447'
chicago: 'Lucek, Kay, Mabel D. Giménez, Mathieu Joron, Marina Rafajlović, Jeremy
B. Searle, Nora Walden, Anja M Westram, and Rui Faria. “The Impact of Chromosomal
Rearrangements in Speciation: From Micro- to Macroevolution.” Cold Spring Harbor
Perspectives in Biology. Cold Spring Harbor Laboratory, 2023. https://doi.org/10.1101/cshperspect.a041447.'
ieee: 'K. Lucek et al., “The impact of chromosomal rearrangements in speciation:
From micro- to macroevolution,” Cold Spring Harbor Perspectives in Biology,
vol. 15, no. 11. Cold Spring Harbor Laboratory, 2023.'
ista: 'Lucek K, Giménez MD, Joron M, Rafajlović M, Searle JB, Walden N, Westram
AM, Faria R. 2023. The impact of chromosomal rearrangements in speciation: From
micro- to macroevolution. Cold Spring Harbor Perspectives in Biology. 15(11),
a041447.'
mla: 'Lucek, Kay, et al. “The Impact of Chromosomal Rearrangements in Speciation:
From Micro- to Macroevolution.” Cold Spring Harbor Perspectives in Biology,
vol. 15, no. 11, a041447, Cold Spring Harbor Laboratory, 2023, doi:10.1101/cshperspect.a041447.'
short: K. Lucek, M.D. Giménez, M. Joron, M. Rafajlović, J.B. Searle, N. Walden,
A.M. Westram, R. Faria, Cold Spring Harbor Perspectives in Biology 15 (2023).
date_created: 2024-01-08T12:43:48Z
date_published: 2023-11-01T00:00:00Z
date_updated: 2024-01-08T12:52:29Z
day: '01'
department:
- _id: NiBa
- _id: BeVi
doi: 10.1101/cshperspect.a041447
external_id:
pmid:
- '37604585'
intvolume: ' 15'
issue: '11'
keyword:
- General Biochemistry
- Genetics and Molecular Biology
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1101/cshperspect.a041447
month: '11'
oa: 1
oa_version: Published Version
pmid: 1
publication: Cold Spring Harbor Perspectives in Biology
publication_identifier:
issn:
- 1943-0264
publication_status: published
publisher: Cold Spring Harbor Laboratory
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'The impact of chromosomal rearrangements in speciation: From micro- to macroevolution'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15
year: '2023'
...
---
_id: '14743'
abstract:
- lang: eng
text: Leader-based consensus algorithms are fast and efficient under normal conditions,
but lack robustness to adverse conditions due to their reliance on timeouts for
liveness. We present QuePaxa, the first protocol offering state-of-the-art normal-case
efficiency without depending on timeouts. QuePaxa uses a novel randomized asynchronous
consensus core to tolerate adverse conditions such as denial-of-service (DoS)
attacks, while a one-round-trip fast path preserves the normal-case efficiency
of Multi-Paxos or Raft. By allowing simultaneous proposers without destructive
interference, and using short hedging delays instead of conservative timeouts
to limit redundant effort, QuePaxa permits rapid recovery after leader failure
without risking costly view changes due to false timeouts. By treating leader
choice and hedging delay as a multi-armed-bandit optimization, QuePaxa achieves
responsiveness to prevalent conditions, and can choose the best leader even if
the current one has not failed. Experiments with a prototype confirm that QuePaxa
achieves normal-case LAN and WAN performance of 584k and 250k cmd/sec in throughput,
respectively, comparable to Multi-Paxos. Under conditions such as DoS attacks,
misconfigurations, or slow leaders that severely impact existing protocols, we
find that QuePaxa remains live with median latency under 380ms in WAN experiments.
acknowledgement: The authors would like to thank Marcos K. Aguilera, Pierluca Borsò,
Aleksey Charapko, Rachid Guerraoui, Jovan Komatovic, Derek Leung, Louis-Henri Merino,
Shailesh Mishra, Haochen Pan, Rodrigo Rodrigues, Lewis Tseng, and Haoqian Zhang
for their helpful feedback on early drafts of this paper.
article_processing_charge: No
author:
- first_name: Pasindu
full_name: Tennage, Pasindu
last_name: Tennage
- first_name: Cristina
full_name: Basescu, Cristina
last_name: Basescu
- first_name: Eleftherios
full_name: Kokoris Kogias, Eleftherios
id: f5983044-d7ef-11ea-ac6d-fd1430a26d30
last_name: Kokoris Kogias
- first_name: Ewa
full_name: Syta, Ewa
last_name: Syta
- first_name: Philipp
full_name: Jovanovic, Philipp
last_name: Jovanovic
- first_name: Vero
full_name: Estrada-Galinanes, Vero
last_name: Estrada-Galinanes
- first_name: Bryan
full_name: Ford, Bryan
last_name: Ford
citation:
ama: 'Tennage P, Basescu C, Kokoris Kogias E, et al. QuePaxa: Escaping the tyranny
of timeouts in consensus. In: Proceedings of the 29th Symposium on Operating
Systems Principles. Association for Computing Machinery; 2023:281-297. doi:10.1145/3600006.3613150'
apa: 'Tennage, P., Basescu, C., Kokoris Kogias, E., Syta, E., Jovanovic, P., Estrada-Galinanes,
V., & Ford, B. (2023). QuePaxa: Escaping the tyranny of timeouts in consensus.
In Proceedings of the 29th Symposium on Operating Systems Principles (pp.
281–297). Koblenz, Germany: Association for Computing Machinery. https://doi.org/10.1145/3600006.3613150'
chicago: 'Tennage, Pasindu, Cristina Basescu, Eleftherios Kokoris Kogias, Ewa Syta,
Philipp Jovanovic, Vero Estrada-Galinanes, and Bryan Ford. “QuePaxa: Escaping
the Tyranny of Timeouts in Consensus.” In Proceedings of the 29th Symposium
on Operating Systems Principles, 281–97. Association for Computing Machinery,
2023. https://doi.org/10.1145/3600006.3613150.'
ieee: 'P. Tennage et al., “QuePaxa: Escaping the tyranny of timeouts in consensus,”
in Proceedings of the 29th Symposium on Operating Systems Principles, Koblenz,
Germany, 2023, pp. 281–297.'
ista: 'Tennage P, Basescu C, Kokoris Kogias E, Syta E, Jovanovic P, Estrada-Galinanes
V, Ford B. 2023. QuePaxa: Escaping the tyranny of timeouts in consensus. Proceedings
of the 29th Symposium on Operating Systems Principles. SOSP: Symposium on Operating
Systems Principles, 281–297.'
mla: 'Tennage, Pasindu, et al. “QuePaxa: Escaping the Tyranny of Timeouts in Consensus.”
Proceedings of the 29th Symposium on Operating Systems Principles, Association
for Computing Machinery, 2023, pp. 281–97, doi:10.1145/3600006.3613150.'
short: P. Tennage, C. Basescu, E. Kokoris Kogias, E. Syta, P. Jovanovic, V. Estrada-Galinanes,
B. Ford, in:, Proceedings of the 29th Symposium on Operating Systems Principles,
Association for Computing Machinery, 2023, pp. 281–297.
conference:
end_date: 2023-10-26
location: Koblenz, Germany
name: 'SOSP: Symposium on Operating Systems Principles'
start_date: 2023-10-23
date_created: 2024-01-08T12:54:35Z
date_published: 2023-10-01T00:00:00Z
date_updated: 2024-02-28T12:51:24Z
day: '01'
department:
- _id: ElKo
doi: 10.1145/3600006.3613150
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1145/3600006.3613150
month: '10'
oa: 1
oa_version: Published Version
page: 281-297
publication: Proceedings of the 29th Symposium on Operating Systems Principles
publication_identifier:
isbn:
- '9798400702297'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'QuePaxa: Escaping the tyranny of timeouts in consensus'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...
---
_id: '14750'
abstract:
- lang: eng
text: "Consider the random matrix model A1/2UBU∗A1/2, where A and B are two N ×
N deterministic matrices and U is either an N × N Haar unitary or orthogonal random
matrix. It is well known that on the macroscopic scale (Invent. Math. 104 (1991)
201–220), the limiting empirical spectral distribution (ESD) of the above model
is given by the free multiplicative convolution\r\nof the limiting ESDs of A and
B, denoted as μα \x02 μβ, where μα and μβ are the limiting ESDs of A and B, respectively.
In this paper, we study the asymptotic microscopic behavior of the edge eigenvalues
and eigenvectors statistics. We prove that both the density of μA \x02μB, where
μA and μB are the ESDs of A and B, respectively and the associated subordination
functions\r\nhave a regular behavior near the edges. Moreover, we establish the
local laws near the edges on the optimal scale. In particular, we prove that the
entries of the resolvent are close to some functionals depending only on the eigenvalues
of A, B and the subordination functions with optimal convergence rates. Our proofs
and calculations are based on the techniques developed for the additive model
A+UBU∗ in (J. Funct. Anal. 271 (2016) 672–719; Comm. Math.\r\nPhys. 349 (2017)
947–990; Adv. Math. 319 (2017) 251–291; J. Funct. Anal. 279 (2020) 108639), and
our results can be regarded as the counterparts of (J. Funct. Anal. 279 (2020)
108639) for the multiplicative model. "
acknowledgement: "The first author is partially supported by NSF Grant DMS-2113489
and grateful for the AMS-SIMONS travel grant (2020–2023). The second author is supported
by the ERC Advanced Grant “RMTBeyond” No. 101020331.\r\nThe authors would like to
thank the Editor, Associate Editor and an anonymous referee for their many critical
suggestions which have significantly improved the paper. We also want to thank Zhigang
Bao and Ji Oon Lee for many helpful discussions and comments."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Xiucai
full_name: Ding, Xiucai
last_name: Ding
- first_name: Hong Chang
full_name: Ji, Hong Chang
id: dd216c0a-c1f9-11eb-beaf-e9ea9d2de76d
last_name: Ji
citation:
ama: Ding X, Ji HC. Local laws for multiplication of random matrices. The Annals
of Applied Probability. 2023;33(4):2981-3009. doi:10.1214/22-aap1882
apa: Ding, X., & Ji, H. C. (2023). Local laws for multiplication of random matrices.
The Annals of Applied Probability. Institute of Mathematical Statistics.
https://doi.org/10.1214/22-aap1882
chicago: Ding, Xiucai, and Hong Chang Ji. “Local Laws for Multiplication of Random
Matrices.” The Annals of Applied Probability. Institute of Mathematical
Statistics, 2023. https://doi.org/10.1214/22-aap1882.
ieee: X. Ding and H. C. Ji, “Local laws for multiplication of random matrices,”
The Annals of Applied Probability, vol. 33, no. 4. Institute of Mathematical
Statistics, pp. 2981–3009, 2023.
ista: Ding X, Ji HC. 2023. Local laws for multiplication of random matrices. The
Annals of Applied Probability. 33(4), 2981–3009.
mla: Ding, Xiucai, and Hong Chang Ji. “Local Laws for Multiplication of Random Matrices.”
The Annals of Applied Probability, vol. 33, no. 4, Institute of Mathematical
Statistics, 2023, pp. 2981–3009, doi:10.1214/22-aap1882.
short: X. Ding, H.C. Ji, The Annals of Applied Probability 33 (2023) 2981–3009.
date_created: 2024-01-08T13:03:18Z
date_published: 2023-08-01T00:00:00Z
date_updated: 2024-01-09T08:16:41Z
day: '01'
department:
- _id: LaEr
doi: 10.1214/22-aap1882
ec_funded: 1
external_id:
arxiv:
- '2010.16083'
intvolume: ' 33'
issue: '4'
keyword:
- Statistics
- Probability and Uncertainty
- Statistics and Probability
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2010.16083
month: '08'
oa: 1
oa_version: Preprint
page: 2981-3009
project:
- _id: 62796744-2b32-11ec-9570-940b20777f1d
call_identifier: H2020
grant_number: '101020331'
name: Random matrices beyond Wigner-Dyson-Mehta
publication: The Annals of Applied Probability
publication_identifier:
issn:
- 1050-5164
publication_status: published
publisher: Institute of Mathematical Statistics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Local laws for multiplication of random matrices
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 33
year: '2023'
...
---
_id: '14751'
abstract:
- lang: eng
text: 'We consider zero-error communication over a two-transmitter deterministic
adversarial multiple access channel (MAC) governed by an adversary who has access
to the transmissions of both senders (hence called omniscient ) and aims to maliciously
corrupt the communication. None of the encoders, jammer and decoder is allowed
to randomize using private or public randomness. This enforces a combinatorial
nature of the problem. Our model covers a large family of channels studied in
the literature, including all deterministic discrete memoryless noisy or noiseless
MACs. In this work, given an arbitrary two-transmitter deterministic omniscient
adversarial MAC, we characterize when the capacity region: 1) has nonempty interior
(in particular, is two-dimensional); 2) consists of two line segments (in particular,
has empty interior); 3) consists of one line segment (in particular, is one-dimensional);
4) or only contains (0,0) (in particular, is zero-dimensional). This extends a
recent result by Wang et al. (201 9) from the point-to-point setting to the multiple
access setting. Indeed, our converse arguments build upon their generalized Plotkin
bound and involve delicate case analysis. One of the technical challenges is to
take care of both “joint confusability” and “marginal confusability”. In particular,
the treatment of marginal confusability does not follow from the point-to-point
results by Wang et al. Our achievability results follow from random coding with
expurgation.'
acknowledgement: "The author would like to thank Amitalok J. Budkuley and Sidharth
Jaggi for many helpful discussions at the early stage of this work. He would also
like to thank Nir Ailon, Qi Cao, and Chandra Nair for discussions on a related problem
regarding zero-error binary adder MACs.\r\nThe work of Yihan Zhang was supported
by the European Union’s Horizon 2020 Research and Innovation Programme under Grant
682203-ERC-[Inf-Speed-Tradeoff]"
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Yihan
full_name: Zhang, Yihan
id: 2ce5da42-b2ea-11eb-bba5-9f264e9d002c
last_name: Zhang
orcid: 0000-0002-6465-6258
citation:
ama: Zhang Y. Zero-error communication over adversarial MACs. IEEE Transactions
on Information Theory. 2023;69(7):4093-4127. doi:10.1109/tit.2023.3257239
apa: Zhang, Y. (2023). Zero-error communication over adversarial MACs. IEEE Transactions
on Information Theory. Institute of Electrical and Electronics Engineers.
https://doi.org/10.1109/tit.2023.3257239
chicago: Zhang, Yihan. “Zero-Error Communication over Adversarial MACs.” IEEE
Transactions on Information Theory. Institute of Electrical and Electronics
Engineers, 2023. https://doi.org/10.1109/tit.2023.3257239.
ieee: Y. Zhang, “Zero-error communication over adversarial MACs,” IEEE Transactions
on Information Theory, vol. 69, no. 7. Institute of Electrical and Electronics
Engineers, pp. 4093–4127, 2023.
ista: Zhang Y. 2023. Zero-error communication over adversarial MACs. IEEE Transactions
on Information Theory. 69(7), 4093–4127.
mla: Zhang, Yihan. “Zero-Error Communication over Adversarial MACs.” IEEE Transactions
on Information Theory, vol. 69, no. 7, Institute of Electrical and Electronics
Engineers, 2023, pp. 4093–127, doi:10.1109/tit.2023.3257239.
short: Y. Zhang, IEEE Transactions on Information Theory 69 (2023) 4093–4127.
date_created: 2024-01-08T13:04:54Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2024-01-09T08:45:24Z
day: '01'
department:
- _id: MaMo
doi: 10.1109/tit.2023.3257239
external_id:
arxiv:
- '2101.12426'
intvolume: ' 69'
issue: '7'
keyword:
- Computer Science Applications
- Information Systems
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2101.12426
month: '07'
oa: 1
oa_version: Preprint
page: 4093-4127
publication: IEEE Transactions on Information Theory
publication_identifier:
eissn:
- 1557-9654
issn:
- 0018-9448
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: Zero-error communication over adversarial MACs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 69
year: '2023'
...
---
_id: '14752'
abstract:
- lang: eng
text: 'Radiative cooling of the lowest atmospheric levels is of strong importance
for modulating atmospheric circulations and organizing convection, but detailed
observations and a robust theoretical understanding are lacking. Here we use unprecedented
observational constraints from subsidence regimes in the tropical Atlantic to
develop a theory for the shape and magnitude of low‐level longwave radiative cooling
in clear‐sky, showing peaks larger than 5–10 K/day at the top of the boundary
layer. A suite of novel scaling approximations is first developed from simplified
spectral theory, in close agreement with the measurements. The radiative cooling
peak height is set by the maximum lapse rate in water vapor path, and its magnitude
is mainly controlled by the ratio of column relative humidity above and below
the peak. We emphasize how elevated intrusions of moist air can reduce low‐level
cooling, by sporadically shading the spectral range which effectively cools to
space. The efficiency of this spectral shading depends both on water content and
altitude of moist intrusions; its height dependence cannot be explained by the
temperature difference between the emitting and absorbing layers, but by the decrease
of water vapor extinction with altitude. This analytical work can help to narrow
the search for low‐level cloud patterns sensitive to radiative‐convective feedbacks:
the most organized patterns with largest cloud fractions occur in atmospheres
below 10% relative humidity and feel the strongest low‐level cooling. This motivates
further assessment of favorable conditions for radiative‐convective feedbacks
and a robust quantification of corresponding shallow cloud dynamics in current
and warmer climates.'
acknowledgement: The authors would like to thank two anonymous reviews and gratefully
acknowledge diverse funding agencies and resources used for this work. B.F. and
C.M. thank funding from the European Research Council (ERC) under the European Union's
Horizon 2020 research and innovation program (Project CLUSTER, grant agreement no.
805041), and the EUREC4A campaign organizers for giving the opportunity to take
part to the campaign and use the data early on. R. P. was supported by the US National
Science Foundation (award AGS 19–16908), by the National Oceanic and Atmospheric
Administration (award NA200AR4310375), and the Vetlesen Foundation.
article_number: e2023AV000880
article_processing_charge: Yes
article_type: original
author:
- first_name: B.
full_name: Fildier, B.
last_name: Fildier
- first_name: Caroline J
full_name: Muller, Caroline J
id: f978ccb0-3f7f-11eb-b193-b0e2bd13182b
last_name: Muller
orcid: 0000-0001-5836-5350
- first_name: R.
full_name: Pincus, R.
last_name: Pincus
- first_name: S.
full_name: Fueglistaler, S.
last_name: Fueglistaler
citation:
ama: Fildier B, Muller CJ, Pincus R, Fueglistaler S. How moisture shapes low‐level
radiative cooling in subsidence regimes. AGU Advances. 2023;4(3). doi:10.1029/2023av000880
apa: Fildier, B., Muller, C. J., Pincus, R., & Fueglistaler, S. (2023). How
moisture shapes low‐level radiative cooling in subsidence regimes. AGU Advances.
American Geophysical Union. https://doi.org/10.1029/2023av000880
chicago: Fildier, B., Caroline J Muller, R. Pincus, and S. Fueglistaler. “How Moisture
Shapes Low‐level Radiative Cooling in Subsidence Regimes.” AGU Advances.
American Geophysical Union, 2023. https://doi.org/10.1029/2023av000880.
ieee: B. Fildier, C. J. Muller, R. Pincus, and S. Fueglistaler, “How moisture shapes
low‐level radiative cooling in subsidence regimes,” AGU Advances, vol.
4, no. 3. American Geophysical Union, 2023.
ista: Fildier B, Muller CJ, Pincus R, Fueglistaler S. 2023. How moisture shapes
low‐level radiative cooling in subsidence regimes. AGU Advances. 4(3), e2023AV000880.
mla: Fildier, B., et al. “How Moisture Shapes Low‐level Radiative Cooling in Subsidence
Regimes.” AGU Advances, vol. 4, no. 3, e2023AV000880, American Geophysical
Union, 2023, doi:10.1029/2023av000880.
short: B. Fildier, C.J. Muller, R. Pincus, S. Fueglistaler, AGU Advances 4 (2023).
date_created: 2024-01-08T13:07:49Z
date_published: 2023-06-01T00:00:00Z
date_updated: 2024-01-09T08:54:03Z
day: '01'
ddc:
- '550'
department:
- _id: CaMu
doi: 10.1029/2023av000880
ec_funded: 1
file:
- access_level: open_access
checksum: af773220a9fa194c61a8dc2fae092c16
content_type: application/pdf
creator: dernst
date_created: 2024-01-09T08:51:25Z
date_updated: 2024-01-09T08:51:25Z
file_id: '14761'
file_name: 2023_AGUAdvances_Fildier.pdf
file_size: 24149551
relation: main_file
success: 1
file_date_updated: 2024-01-09T08:51:25Z
has_accepted_license: '1'
intvolume: ' 4'
issue: '3'
keyword:
- General Earth and Planetary Sciences
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
project:
- _id: 629205d8-2b32-11ec-9570-e1356ff73576
call_identifier: H2020
grant_number: '805041'
name: organization of CLoUdS, and implications of Tropical cyclones and for the
Energetics of the tropics, in current and waRming climate
publication: AGU Advances
publication_identifier:
eissn:
- 2576-604X
publication_status: published
publisher: American Geophysical Union
quality_controlled: '1'
scopus_import: '1'
status: public
title: How moisture shapes low‐level radiative cooling in subsidence regimes
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
(CC BY-NC-ND 4.0)
short: CC BY-NC-ND (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2023'
...
---
_id: '14753'
abstract:
- lang: eng
text: "Several fixed-target experiments reported J/ψ and ϒ polarizations, as functions
of Feynman x (xF) and transverse momentum (PT), in three different frames, using
different combinations of beam particles, target nuclei, and collision energies.
Despite the diverse and heterogeneous picture formed by these measurements, a
detailed look allows us to discern qualitative physical patterns that inspire
a simple empirical model. This data-driven scenario offers a good quantitative
description of the J/ψ and ϒ(1S) polarizations measured in proton- and pion-nucleus
collisions, in the xF 0.5 domain: more than 80 data points (not statistically
independent) are well reproduced with only one free parameter. This study sets
the context for future low-PT\r\n quarkonium polarization measurements in proton-
and pion-nucleus collisions, such as those to be made by the AMBER experiment,
and shows that such measurements provide significant constraints on the poorly-known
parton distribution functions of the pion."
acknowledgement: "P.F. and C.L. acknowledge support from Fundação para a Ciência e
a Tecnologia, Portugal, under contract CERN/FIS-PAR/0010/2019.\r\nOpen Access funded
by SCOAP3."
article_number: '137871'
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Pietro
full_name: Faccioli, Pietro
last_name: Faccioli
- first_name: Ilse
full_name: Krätschmer, Ilse
id: 30d4014e-7753-11eb-b44b-db6d61112e73
last_name: Krätschmer
orcid: 0000-0002-5636-9259
- first_name: Carlos
full_name: Lourenço, Carlos
last_name: Lourenço
citation:
ama: 'Faccioli P, Krätschmer I, Lourenço C. Low-pT quarkonium polarization measurements:
Challenges and opportunities. Physics Letters B. 2023;840. doi:10.1016/j.physletb.2023.137871'
apa: 'Faccioli, P., Krätschmer, I., & Lourenço, C. (2023). Low-pT quarkonium
polarization measurements: Challenges and opportunities. Physics Letters B.
Elsevier. https://doi.org/10.1016/j.physletb.2023.137871'
chicago: 'Faccioli, Pietro, Ilse Krätschmer, and Carlos Lourenço. “Low-PT Quarkonium
Polarization Measurements: Challenges and Opportunities.” Physics Letters B.
Elsevier, 2023. https://doi.org/10.1016/j.physletb.2023.137871.'
ieee: 'P. Faccioli, I. Krätschmer, and C. Lourenço, “Low-pT quarkonium polarization
measurements: Challenges and opportunities,” Physics Letters B, vol. 840.
Elsevier, 2023.'
ista: 'Faccioli P, Krätschmer I, Lourenço C. 2023. Low-pT quarkonium polarization
measurements: Challenges and opportunities. Physics Letters B. 840, 137871.'
mla: 'Faccioli, Pietro, et al. “Low-PT Quarkonium Polarization Measurements: Challenges
and Opportunities.” Physics Letters B, vol. 840, 137871, Elsevier, 2023,
doi:10.1016/j.physletb.2023.137871.'
short: P. Faccioli, I. Krätschmer, C. Lourenço, Physics Letters B 840 (2023).
date_created: 2024-01-08T13:09:17Z
date_published: 2023-05-10T00:00:00Z
date_updated: 2024-01-09T09:02:22Z
day: '10'
ddc:
- '530'
department:
- _id: MaRo
doi: 10.1016/j.physletb.2023.137871
file:
- access_level: open_access
checksum: 02dec160dbc81d95985e755869d8afbf
content_type: application/pdf
creator: dernst
date_created: 2024-01-09T08:59:24Z
date_updated: 2024-01-09T08:59:24Z
file_id: '14762'
file_name: 2023_PhysicsLettersB_Faccioli.pdf
file_size: 855494
relation: main_file
success: 1
file_date_updated: 2024-01-09T08:59:24Z
has_accepted_license: '1'
intvolume: ' 840'
keyword:
- Nuclear and High Energy Physics
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
publication: Physics Letters B
publication_identifier:
eissn:
- 1873-2445
issn:
- 0370-2693
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Low-pT quarkonium polarization measurements: Challenges and opportunities'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 840
year: '2023'
...