---
_id: '3175'
abstract:
- lang: eng
text: This paper addresses the novel problem of automatically synthesizing an output
image from a large collection of different input images. The synthesized image,
called a digital tapestry, can be viewed as a visual summary or a virtual 'thumbnail'
of all the images in the input collection. The problem of creating the tapestry
is cast as a multi-class labeling problem such that each region in the tapestry
is constructed from input image blocks that are salient and such that neighboring
blocks satisfy spatial compatibility. This is formulated using a Markov Random
Field and optimized via the graph cut based expansion move algorithm. The standard
expansion move algorithm can only handle energies with metric terms, while our
energy contains non-metric (soft and hard) constraints. Therefore we propose two
novel contributions. First, we extend the expansion move algorithm for energy
functions with non-metric hard constraints. Secondly, we modify it for functions
with "almost" metric soft terms, and show that it gives good results
in practice. The proposed framework was tested on several consumer photograph
collections, and the results are presented.
author:
- first_name: Carsten
full_name: Rother, Carsten
last_name: Rother
- first_name: Sanjiv
full_name: Kumar, Sanjiv
last_name: Kumar
- first_name: Vladimir
full_name: Vladimir Kolmogorov
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Andrew
full_name: Blake, Andrew
last_name: Blake
citation:
ama: 'Rother C, Kumar S, Kolmogorov V, Blake A. Digital tapestry. In: Vol 1. IEEE;
2005:589-596. doi:10.1109/CVPR.2005.130'
apa: 'Rother, C., Kumar, S., Kolmogorov, V., & Blake, A. (2005). Digital tapestry
(Vol. 1, pp. 589–596). Presented at the CVPR: Computer Vision and Pattern Recognition,
IEEE. https://doi.org/10.1109/CVPR.2005.130'
chicago: Rother, Carsten, Sanjiv Kumar, Vladimir Kolmogorov, and Andrew Blake. “Digital
Tapestry,” 1:589–96. IEEE, 2005. https://doi.org/10.1109/CVPR.2005.130.
ieee: 'C. Rother, S. Kumar, V. Kolmogorov, and A. Blake, “Digital tapestry,” presented
at the CVPR: Computer Vision and Pattern Recognition, 2005, vol. 1, pp. 589–596.'
ista: 'Rother C, Kumar S, Kolmogorov V, Blake A. 2005. Digital tapestry. CVPR: Computer
Vision and Pattern Recognition vol. 1, 589–596.'
mla: Rother, Carsten, et al. Digital Tapestry. Vol. 1, IEEE, 2005, pp. 589–96,
doi:10.1109/CVPR.2005.130.
short: C. Rother, S. Kumar, V. Kolmogorov, A. Blake, in:, IEEE, 2005, pp. 589–596.
conference:
name: 'CVPR: Computer Vision and Pattern Recognition'
date_created: 2018-12-11T12:01:50Z
date_published: 2005-07-25T00:00:00Z
date_updated: 2021-01-12T07:41:35Z
day: '25'
doi: 10.1109/CVPR.2005.130
extern: 1
intvolume: ' 1'
main_file_link:
- open_access: '0'
url: http://research.microsoft.com/en-us/um/people/ablake/papers/ablake/rother_cvpr05.pdf
month: '07'
page: 589 - 596
publication_status: published
publisher: IEEE
publist_id: '3503'
quality_controlled: 0
status: public
title: Digital tapestry
type: conference
volume: 1
year: '2005'
...
---
_id: '3176'
abstract:
- lang: eng
text: |
This paper demonstrates the high quality, real-time segmentation techniques. We achieve real-time segmentation of foreground from background layers in stereo video sequences. Automatic separation of layers from colour/contrast or from stereo alone is known to be error-prone. Here, colour, contrast and stereo matching information are fused to infer layers accurately and efficiently. The first algorithm, layered dynamic programming (LDP), solves stereo in an extended 6-state space that represents both foreground/background layers and occluded regions. The stereo-match likelihood is then fused with a contrast-sensitive colour model that is learned on the fly, and stereo disparities are obtained by dynamic programming. The second algorithm, layered graph cut (LGC), does not directly solve stereo. Instead the stereo match likelihood is marginalised over foreground and background hypotheses, and fused with a contrast-sensitive colour model like the one used in LDP. Segmentation is solved efficiently by ternary graph cut. Both algorithms are evaluated with respect to ground truth data and found to have similar performance, substantially better than stereo or colour/contrast alone. However, their characteristics with respect to computational efficiency are rather different. The algorithms are demonstrated in the application of background substitution and shown to give good quality composite video output.
author:
- first_name: Vladimir
full_name: Vladimir Kolmogorov
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Antonio
full_name: Criminisi, Antonio
last_name: Criminisi
- first_name: Andrew
full_name: Blake, Andrew
last_name: Blake
- first_name: Geoffrey
full_name: Cross, Geoffrey
last_name: Cross
- first_name: Carsten
full_name: Rother, Carsten
last_name: Rother
citation:
ama: 'Kolmogorov V, Criminisi A, Blake A, Cross G, Rother C. Bi-layer segmentation
of binocular stereo video. In: IEEE; 2005:1186-1186. doi:10.1109/CVPR.2005.90'
apa: 'Kolmogorov, V., Criminisi, A., Blake, A., Cross, G., & Rother, C. (2005).
Bi-layer segmentation of binocular stereo video (pp. 1186–1186). Presented at
the CVPR: Computer Vision and Pattern Recognition, IEEE. https://doi.org/10.1109/CVPR.2005.90'
chicago: Kolmogorov, Vladimir, Antonio Criminisi, Andrew Blake, Geoffrey Cross,
and Carsten Rother. “Bi-Layer Segmentation of Binocular Stereo Video,” 1186–1186.
IEEE, 2005. https://doi.org/10.1109/CVPR.2005.90.
ieee: 'V. Kolmogorov, A. Criminisi, A. Blake, G. Cross, and C. Rother, “Bi-layer
segmentation of binocular stereo video,” presented at the CVPR: Computer Vision
and Pattern Recognition, 2005, pp. 1186–1186.'
ista: 'Kolmogorov V, Criminisi A, Blake A, Cross G, Rother C. 2005. Bi-layer segmentation
of binocular stereo video. CVPR: Computer Vision and Pattern Recognition, 1186–1186.'
mla: Kolmogorov, Vladimir, et al. Bi-Layer Segmentation of Binocular Stereo Video.
IEEE, 2005, pp. 1186–1186, doi:10.1109/CVPR.2005.90.
short: V. Kolmogorov, A. Criminisi, A. Blake, G. Cross, C. Rother, in:, IEEE, 2005,
pp. 1186–1186.
conference:
name: 'CVPR: Computer Vision and Pattern Recognition'
date_created: 2018-12-11T12:01:50Z
date_published: 2005-01-01T00:00:00Z
date_updated: 2021-01-12T07:41:35Z
day: '01'
doi: 10.1109/CVPR.2005.90
extern: 1
month: '01'
page: 1186 - 1186
publication_status: published
publisher: IEEE
publist_id: '3504'
quality_controlled: 0
status: public
title: Bi-layer segmentation of binocular stereo video
type: conference
year: '2005'
...
---
_id: '3181'
abstract:
- lang: eng
text: Tree-reweighted max-product (TRW) message passing [9] is a modified form of
the ordinary max-product algorithm for attempting to find minimal energy configurations
in Markov random field with cycles. For a TRW fixed point satisfying the strong
tree agreement condition, the algorithm outputs a configuration that is provably
optimal. In this paper, we focus on the case of binary variables with pairwise
couplings, and establish stronger properties of TRW fixed points that satisfy
only the milder condition of weak tree agreement (WTA). First, we demonstrate
how it is possible to identify part of the optimal solution - i.e., a provably
optimal solution for a subset of nodes - without knowing a complete solution.
Second, we show that for submodular functions, a WTA fixed point always yields
a globally optimal solution. We establish that for binary variables, any WTA fixed
point always achieves the global maximum of the linear programming relaxation
underlying the TRW method.
author:
- first_name: Vladimir
full_name: Vladimir Kolmogorov
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Martin
full_name: Wainwright, Martin J
last_name: Wainwright
citation:
ama: 'Kolmogorov V, Wainwright M. On the optimality of tree reweighted max product
message passing. In: AUAI Press; 2005:316-323.'
apa: 'Kolmogorov, V., & Wainwright, M. (2005). On the optimality of tree reweighted
max product message passing (pp. 316–323). Presented at the UAI: Uncertainty in
Artificial Intelligence, AUAI Press.'
chicago: Kolmogorov, Vladimir, and Martin Wainwright. “On the Optimality of Tree
Reweighted Max Product Message Passing,” 316–23. AUAI Press, 2005.
ieee: 'V. Kolmogorov and M. Wainwright, “On the optimality of tree reweighted max
product message passing,” presented at the UAI: Uncertainty in Artificial Intelligence,
2005, pp. 316–323.'
ista: 'Kolmogorov V, Wainwright M. 2005. On the optimality of tree reweighted max
product message passing. UAI: Uncertainty in Artificial Intelligence, 316–323.'
mla: Kolmogorov, Vladimir, and Martin Wainwright. On the Optimality of Tree Reweighted
Max Product Message Passing. AUAI Press, 2005, pp. 316–23.
short: V. Kolmogorov, M. Wainwright, in:, AUAI Press, 2005, pp. 316–323.
conference:
name: 'UAI: Uncertainty in Artificial Intelligence'
date_created: 2018-12-11T12:01:51Z
date_published: 2005-07-01T00:00:00Z
date_updated: 2021-01-12T07:41:38Z
day: '01'
extern: 1
main_file_link:
- open_access: '0'
url: http://research.microsoft.com/pubs/67405/trw_opt_uai05.pdf
month: '07'
page: 316 - 323
publication_status: published
publisher: AUAI Press
publist_id: '3500'
quality_controlled: 0
status: public
title: On the optimality of tree reweighted max product message passing
type: conference
year: '2005'
...
---
_id: '3182'
abstract:
- lang: eng
text: In the work of the authors (2003), we showed that graph cuts can find hypersurfaces
of globally minimal length (or area) under any Riemannian metric. Here we show
that graph cuts on directed regular grids can approximate a significantly more
general class of continuous non-symmetric metrics. Using submodularity condition
(Boros and Hammer, 2002 and Kolmogorov and Zabih, 2004), we obtain a tight characterization
of graph-representable metrics. Such "submodular" metrics have an elegant
geometric interpretation via hypersurface functionals combining length/area and
flux. Practically speaking, we attend 'geo-cuts' algorithm to a wider class of
geometrically motivated hypersurface functionals and show how to globally optimize
any combination of length/area and flux of a given vector field. The concept of
flux was recently introduced into computer vision by Vasilevskiy and Siddiqi (2002)
but it was mainly studied within variational framework so far. We are first to
show that flux can be integrated into graph cuts as well. Combining geometric
concepts of flux and length/area within the global optimization framework of graph
cuts allows principled discrete segmentation models and advances the slate of
the art for the graph cuts methods in vision. In particular we address the "shrinking"
problem of graph cuts, improve segmentation of long thin objects, and introduce
useful shape constraints.
author:
- first_name: Vladimir
full_name: Vladimir Kolmogorov
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Yuri
full_name: Boykov, Yuri
last_name: Boykov
citation:
ama: 'Kolmogorov V, Boykov Y. What metrics can be approximated by geo cuts or global
optimization of length area and flux. In: Vol 1. IEEE; 2005:564-571. doi:10.1109/ICCV.2005.252'
apa: 'Kolmogorov, V., & Boykov, Y. (2005). What metrics can be approximated
by geo cuts or global optimization of length area and flux (Vol. 1, pp. 564–571).
Presented at the ICCV: International Conference on Computer Vision, IEEE. https://doi.org/10.1109/ICCV.2005.252'
chicago: Kolmogorov, Vladimir, and Yuri Boykov. “What Metrics Can Be Approximated
by Geo Cuts or Global Optimization of Length Area and Flux,” 1:564–71. IEEE, 2005.
https://doi.org/10.1109/ICCV.2005.252.
ieee: 'V. Kolmogorov and Y. Boykov, “What metrics can be approximated by geo cuts
or global optimization of length area and flux,” presented at the ICCV: International
Conference on Computer Vision, 2005, vol. 1, pp. 564–571.'
ista: 'Kolmogorov V, Boykov Y. 2005. What metrics can be approximated by geo cuts
or global optimization of length area and flux. ICCV: International Conference
on Computer Vision vol. 1, 564–571.'
mla: Kolmogorov, Vladimir, and Yuri Boykov. What Metrics Can Be Approximated
by Geo Cuts or Global Optimization of Length Area and Flux. Vol. 1, IEEE,
2005, pp. 564–71, doi:10.1109/ICCV.2005.252.
short: V. Kolmogorov, Y. Boykov, in:, IEEE, 2005, pp. 564–571.
conference:
name: 'ICCV: International Conference on Computer Vision'
date_created: 2018-12-11T12:01:52Z
date_published: 2005-12-05T00:00:00Z
date_updated: 2021-01-12T07:41:38Z
day: '05'
doi: 10.1109/ICCV.2005.252
extern: 1
intvolume: ' 1'
month: '12'
page: 564 - 571
publication_status: published
publisher: IEEE
publist_id: '3501'
quality_controlled: 0
status: public
title: What metrics can be approximated by geo cuts or global optimization of length
area and flux
type: conference
volume: 1
year: '2005'
...
---
_id: '3183'
abstract:
- lang: eng
text: This paper describes two algorithms capable of real-time segmentation of foreground
from background layers in stereo video sequences. Automatic separation of layers
from colour/contrast or from stereo alone is known to be error-prone. Here, colour,
contrast and stereo matching information are fused to infer layers accurately
and efficiently. The first algorithm, Layered Dynamic Programming (LDP), solves
stereo in an extended 6-state space that represents both foreground/background
layers and occluded regions. The stereo-match likelihood is then fused with a
contrast-sensitive colour model that is learned on the fly, and stereo disparities
are obtained by dynamic programming. The second algorithm, Layered Graph Cut (LGC),
does not directly solve stereo. Instead the stereo match likelihood is marginalised
over foreground and background hypotheses, and fused with a contrast-sensitive
colour model like the one used in LDP. Segmentation is solved efficiently by ternary
graph cut. Both algorithms are evaluated with respect to ground truth data and
found to have similar perfomance, substantially better than stereo or colour/contrast
alone. However, their characteristics with respect to computational efficiency
are rather different. The algorithms are demonstrated in the application of background
substitution and shown to give good quality composite video output.
author:
- first_name: Vladimir
full_name: Vladimir Kolmogorov
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Antonio
full_name: Criminisi, Antonio
last_name: Criminisi
- first_name: Andrew
full_name: Blake, Andrew
last_name: Blake
- first_name: Geoffrey
full_name: Cross, Geoffrey
last_name: Cross
- first_name: Carsten
full_name: Rother, Carsten
last_name: Rother
citation:
ama: 'Kolmogorov V, Criminisi A, Blake A, Cross G, Rother C. Bi-layer segmentation
of binocular stereo video. In: Vol 2. IEEE; 2005:407-414. doi:10.1109/CVPR.2005.91'
apa: 'Kolmogorov, V., Criminisi, A., Blake, A., Cross, G., & Rother, C. (2005).
Bi-layer segmentation of binocular stereo video (Vol. 2, pp. 407–414). Presented
at the CVPR: Computer Vision and Pattern Recognition, IEEE. https://doi.org/10.1109/CVPR.2005.91'
chicago: Kolmogorov, Vladimir, Antonio Criminisi, Andrew Blake, Geoffrey Cross,
and Carsten Rother. “Bi-Layer Segmentation of Binocular Stereo Video,” 2:407–14.
IEEE, 2005. https://doi.org/10.1109/CVPR.2005.91.
ieee: 'V. Kolmogorov, A. Criminisi, A. Blake, G. Cross, and C. Rother, “Bi-layer
segmentation of binocular stereo video,” presented at the CVPR: Computer Vision
and Pattern Recognition, 2005, vol. 2, pp. 407–414.'
ista: 'Kolmogorov V, Criminisi A, Blake A, Cross G, Rother C. 2005. Bi-layer segmentation
of binocular stereo video. CVPR: Computer Vision and Pattern Recognition vol.
2, 407–414.'
mla: Kolmogorov, Vladimir, et al. Bi-Layer Segmentation of Binocular Stereo Video.
Vol. 2, IEEE, 2005, pp. 407–14, doi:10.1109/CVPR.2005.91.
short: V. Kolmogorov, A. Criminisi, A. Blake, G. Cross, C. Rother, in:, IEEE, 2005,
pp. 407–414.
conference:
name: 'CVPR: Computer Vision and Pattern Recognition'
date_created: 2018-12-11T12:01:52Z
date_published: 2005-07-25T00:00:00Z
date_updated: 2021-01-12T07:41:38Z
day: '25'
doi: 10.1109/CVPR.2005.91
extern: 1
intvolume: ' 2'
main_file_link:
- open_access: '0'
url: http://research.microsoft.com/pubs/67281/criminisi_cvpr2005.pdf
month: '07'
page: 407 - 414
publication_status: published
publisher: IEEE
publist_id: '3502'
quality_controlled: 0
status: public
title: Bi-layer segmentation of binocular stereo video
type: conference
volume: 2
year: '2005'
...
---
_id: '3211'
abstract:
- lang: eng
text: We present an improved bound on the advantage of any q-query adversary at
distinguishing between the CBC MAC over a random n-bit permutation and a random
function outputting n bits. The result assumes that no message queried is a prefix
of any other, as is the case when all messages to be MACed have the same length.
We go on to give an improved analysis of the encrypted CBC MAC, where there is
no restriction on queried messages. Letting m be the block length of the longest
query, our bounds are about mq2/2n for the basic CBC MAC and mo(1)q2/2n for the
encrypted CBC MAC, improving prior bounds of m2q2/2n. The new bounds translate
into improved guarantees on the probability of forging these MACs.
acknowledgement: Pietrzak was supported by the Swiss National Science Foundation,
project No. 200020-103847/1.
alternative_title:
- LNCS
author:
- first_name: Mihir
full_name: Bellare, Mihir
last_name: Bellare
- first_name: Krzysztof Z
full_name: Krzysztof Pietrzak
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Phillip
full_name: Rogaway, Phillip
last_name: Rogaway
citation:
ama: 'Bellare M, Pietrzak KZ, Rogaway P. Improved security analyses for CBC MACs.
In: Vol 3621. Springer; 2005:527-545. doi:10.1007/11535218_32'
apa: 'Bellare, M., Pietrzak, K. Z., & Rogaway, P. (2005). Improved security
analyses for CBC MACs (Vol. 3621, pp. 527–545). Presented at the CRYPTO: International
Cryptology Conference, Springer. https://doi.org/10.1007/11535218_32'
chicago: Bellare, Mihir, Krzysztof Z Pietrzak, and Phillip Rogaway. “Improved Security
Analyses for CBC MACs,” 3621:527–45. Springer, 2005. https://doi.org/10.1007/11535218_32.
ieee: 'M. Bellare, K. Z. Pietrzak, and P. Rogaway, “Improved security analyses for
CBC MACs,” presented at the CRYPTO: International Cryptology Conference, 2005,
vol. 3621, pp. 527–545.'
ista: 'Bellare M, Pietrzak KZ, Rogaway P. 2005. Improved security analyses for CBC
MACs. CRYPTO: International Cryptology Conference, LNCS, vol. 3621, 527–545.'
mla: Bellare, Mihir, et al. Improved Security Analyses for CBC MACs. Vol.
3621, Springer, 2005, pp. 527–45, doi:10.1007/11535218_32.
short: M. Bellare, K.Z. Pietrzak, P. Rogaway, in:, Springer, 2005, pp. 527–545.
conference:
name: 'CRYPTO: International Cryptology Conference'
date_created: 2018-12-11T12:02:02Z
date_published: 2005-09-12T00:00:00Z
date_updated: 2021-01-12T07:41:50Z
day: '12'
doi: 10.1007/11535218_32
extern: 1
intvolume: ' 3621'
month: '09'
page: 527 - 545
publication_status: published
publisher: Springer
publist_id: '3469'
quality_controlled: 0
status: public
title: Improved security analyses for CBC MACs
type: conference
volume: 3621
year: '2005'
...
---
_id: '3212'
abstract:
- lang: eng
text: |-
The Full-Domain Hash (FDH) signature scheme [3] forms one the most basic usages of random oracles. It works with a family F of trapdoor permutations (TDP), where the signature of m is computed as f−1(h(m)) (here f ∈R F and h is modelled as a random oracle). It is known to be existentially unforgeable for any TDP family F [3], although a much tighter security reduction is known for a restrictive class of TDP’s [10,14] — namely, those induced by a family of claw-free permutations (CFP) pairs. The latter result was shown [11] to match the best possible “black-box” security reduction in the random oracle model, irrespective of the TDP family F (e.g., RSA) one might use.
In this work we investigate the question if it is possible to instantiate the random oracle h with a “real” family of hash functions H such that the corresponding schemes can be proven secure in the standard model, under some natural assumption on the family F. Our main result rules out the existence of such instantiations for any assumption on F which (1) is satisfied by a family of random permutations; and (2) does not allow the attacker to invert f ∈R F on an a-priori unbounded number of points. Moreover, this holds even if the choice of H can arbitrarily depend on f. As an immediate corollary, we rule out instantiating FDH based on general claw-free permutations, which shows that in order to prove the security of FDH in the standard model one must utilize significantly more structure on F than what is sufficient for the best proof of security in the random oracle model.
acknowledgement: Supported by NSF CAREER Award CCR-0133806 and TC Grant No.CCR-0311095.
Supported by the Swiss National Science Foundation, project No. 200020-103847/1
alternative_title:
- LNCS
author:
- first_name: Yevgeniy
full_name: Dodis, Yevgeniy
last_name: Dodis
- first_name: Roberto
full_name: Oliveira, Roberto
last_name: Oliveira
- first_name: Krzysztof Z
full_name: Krzysztof Pietrzak
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Dodis Y, Oliveira R, Pietrzak KZ. On the generic insecurity of the full domain
hash. In: Vol 3621. Springer; 2005:449-466. doi:10.1007/11535218_27'
apa: 'Dodis, Y., Oliveira, R., & Pietrzak, K. Z. (2005). On the generic insecurity
of the full domain hash (Vol. 3621, pp. 449–466). Presented at the CRYPTO: International
Cryptology Conference, Springer. https://doi.org/10.1007/11535218_27'
chicago: Dodis, Yevgeniy, Roberto Oliveira, and Krzysztof Z Pietrzak. “On the Generic
Insecurity of the Full Domain Hash,” 3621:449–66. Springer, 2005. https://doi.org/10.1007/11535218_27.
ieee: 'Y. Dodis, R. Oliveira, and K. Z. Pietrzak, “On the generic insecurity of
the full domain hash,” presented at the CRYPTO: International Cryptology Conference,
2005, vol. 3621, pp. 449–466.'
ista: 'Dodis Y, Oliveira R, Pietrzak KZ. 2005. On the generic insecurity of the
full domain hash. CRYPTO: International Cryptology Conference, LNCS, vol. 3621,
449–466.'
mla: Dodis, Yevgeniy, et al. On the Generic Insecurity of the Full Domain Hash.
Vol. 3621, Springer, 2005, pp. 449–66, doi:10.1007/11535218_27.
short: Y. Dodis, R. Oliveira, K.Z. Pietrzak, in:, Springer, 2005, pp. 449–466.
conference:
name: 'CRYPTO: International Cryptology Conference'
date_created: 2018-12-11T12:02:03Z
date_published: 2005-09-12T00:00:00Z
date_updated: 2021-01-12T07:41:50Z
day: '12'
doi: 10.1007/11535218_27
extern: 1
intvolume: ' 3621'
month: '09'
page: 449 - 466
publication_status: published
publisher: Springer
publist_id: '3470'
quality_controlled: 0
status: public
title: On the generic insecurity of the full domain hash
type: conference
volume: 3621
year: '2005'
...
---
_id: '3213'
abstract:
- lang: eng
text: |-
We study the question whether the sequential or parallel composition of two functions, each indistinguishable from a random function by non-adaptive distinguishers is secure against adaptive distinguishers. The sequential composition of F and G is the function G(F()), the parallel composition is F G where ⋆ is some group operation. It has been shown that composition indeed gives adaptive security in the information theoretic setting, but unfortunately the proof does not translate into the more interesting computational case.
In this work we show that in the computational setting composition does not imply adaptive security: If there is a prime order cyclic group where the decisional Diffie-Hellman assumption holds, then there are functions F and G which are indistinguishable by non-adaptive polynomially time-bounded adversaries, but whose parallel composition can be completely broken (i.e. we recover the key) with only three adaptive queries. We give a similar result for sequential composition. Interestingly, we need a standard assumption from the asymmetric (aka. public-key) world to prove a negative result for symmetric (aka. private-key) systems.
acknowledgement: Supported by the Swiss National Science Foundation, project No. 200020-103847/1.
alternative_title:
- LNCS
author:
- first_name: Krzysztof Z
full_name: Krzysztof Pietrzak
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Pietrzak KZ. Composition does not imply adaptive security. In: Vol 3621. Springer;
2005:55-65. doi:10.1007/11535218_4'
apa: 'Pietrzak, K. Z. (2005). Composition does not imply adaptive security (Vol.
3621, pp. 55–65). Presented at the CRYPTO: International Cryptology Conference,
Springer. https://doi.org/10.1007/11535218_4'
chicago: Pietrzak, Krzysztof Z. “Composition Does Not Imply Adaptive Security,”
3621:55–65. Springer, 2005. https://doi.org/10.1007/11535218_4.
ieee: 'K. Z. Pietrzak, “Composition does not imply adaptive security,” presented
at the CRYPTO: International Cryptology Conference, 2005, vol. 3621, pp. 55–65.'
ista: 'Pietrzak KZ. 2005. Composition does not imply adaptive security. CRYPTO:
International Cryptology Conference, LNCS, vol. 3621, 55–65.'
mla: Pietrzak, Krzysztof Z. Composition Does Not Imply Adaptive Security.
Vol. 3621, Springer, 2005, pp. 55–65, doi:10.1007/11535218_4.
short: K.Z. Pietrzak, in:, Springer, 2005, pp. 55–65.
conference:
name: 'CRYPTO: International Cryptology Conference'
date_created: 2018-12-11T12:02:03Z
date_published: 2005-09-12T00:00:00Z
date_updated: 2021-01-12T07:41:50Z
day: '12'
doi: 10.1007/11535218_4
extern: 1
intvolume: ' 3621'
month: '09'
page: 55 - 65
publication_status: published
publisher: Springer
publist_id: '3468'
quality_controlled: 0
status: public
title: Composition does not imply adaptive security
type: conference
volume: 3621
year: '2005'
...
---
_id: '11120'
abstract:
- lang: eng
text: The nuclear envelope (NE) is a highly specialized membrane that delineates
the eukaryotic cell nucleus. It is composed of the inner and outer nuclear membranes,
nuclear pore complexes (NPCs) and, in metazoa, the lamina. The NE not only regulates
the trafficking of macromolecules between nucleoplasm and cytosol but also provides
anchoring sites for chromatin and the cytoskeleton. Through these interactions,
the NE helps position the nucleus within the cell and chromosomes within the nucleus,
thereby regulating the expression of certain genes. The NE is not static, rather
it is continuously remodeled during cell division. The most dramatic example of
NE reorganization occurs during mitosis in metazoa when the NE undergoes a complete
cycle of disassembly and reformation. Despite the importance of the NE for eukaryotic
cell life, relatively little is known about its biogenesis or many of its functions.
We thus are far from understanding the molecular etiology of a diverse group of
NE-associated diseases.
article_processing_charge: No
article_type: original
author:
- first_name: Martin W
full_name: HETZER, Martin W
id: 86c0d31b-b4eb-11ec-ac5a-eae7b2e135ed
last_name: HETZER
orcid: 0000-0002-2111-992X
- first_name: Tobias C.
full_name: Walther, Tobias C.
last_name: Walther
- first_name: Iain W.
full_name: Mattaj, Iain W.
last_name: Mattaj
citation:
ama: 'Hetzer M, Walther TC, Mattaj IW. Pushing the envelope: Structure, function,
and dynamics of the nuclear periphery. Annual Review of Cell and Developmental
Biology. 2005;21:347-380. doi:10.1146/annurev.cellbio.21.090704.151152'
apa: 'Hetzer, M., Walther, T. C., & Mattaj, I. W. (2005). Pushing the envelope:
Structure, function, and dynamics of the nuclear periphery. Annual Review of
Cell and Developmental Biology. Annual Reviews. https://doi.org/10.1146/annurev.cellbio.21.090704.151152'
chicago: 'Hetzer, Martin, Tobias C. Walther, and Iain W. Mattaj. “Pushing the Envelope:
Structure, Function, and Dynamics of the Nuclear Periphery.” Annual Review
of Cell and Developmental Biology. Annual Reviews, 2005. https://doi.org/10.1146/annurev.cellbio.21.090704.151152.'
ieee: 'M. Hetzer, T. C. Walther, and I. W. Mattaj, “Pushing the envelope: Structure,
function, and dynamics of the nuclear periphery,” Annual Review of Cell and
Developmental Biology, vol. 21. Annual Reviews, pp. 347–380, 2005.'
ista: 'Hetzer M, Walther TC, Mattaj IW. 2005. Pushing the envelope: Structure, function,
and dynamics of the nuclear periphery. Annual Review of Cell and Developmental
Biology. 21, 347–380.'
mla: 'Hetzer, Martin, et al. “Pushing the Envelope: Structure, Function, and Dynamics
of the Nuclear Periphery.” Annual Review of Cell and Developmental Biology,
vol. 21, Annual Reviews, 2005, pp. 347–80, doi:10.1146/annurev.cellbio.21.090704.151152.'
short: M. Hetzer, T.C. Walther, I.W. Mattaj, Annual Review of Cell and Developmental
Biology 21 (2005) 347–380.
date_created: 2022-04-07T07:56:52Z
date_published: 2005-11-10T00:00:00Z
date_updated: 2022-07-18T08:57:34Z
day: '10'
doi: 10.1146/annurev.cellbio.21.090704.151152
extern: '1'
external_id:
pmid:
- '16212499'
intvolume: ' 21'
keyword:
- Cell Biology
- Developmental Biology
language:
- iso: eng
month: '11'
oa_version: None
page: 347-380
pmid: 1
publication: Annual Review of Cell and Developmental Biology
publication_identifier:
eissn:
- 1530-8995
issn:
- 1081-0706
publication_status: published
publisher: Annual Reviews
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Pushing the envelope: Structure, function, and dynamics of the nuclear periphery'
type: journal_article
user_id: 72615eeb-f1f3-11ec-aa25-d4573ddc34fd
volume: 21
year: '2005'
...
---
_id: '11698'
abstract:
- lang: eng
text: We give a short survey of the use of hyperlink analysis in web search engine
ranking and sketch other applications of hyperlink analysis in the web space.
article_processing_charge: No
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: 'Henzinger MH. Hyperlink analysis on the world wide web. In: Proceedings
of the 16th ACM Conference on Hypertext and Hypermedia. Association for Computing
Machinery; 2005:1-3. doi:10.1145/1083356.1083357'
apa: 'Henzinger, M. H. (2005). Hyperlink analysis on the world wide web. In Proceedings
of the 16th ACM conference on Hypertext and hypermedia (pp. 1–3). Salzburg,
Austria: Association for Computing Machinery. https://doi.org/10.1145/1083356.1083357'
chicago: Henzinger, Monika H. “Hyperlink Analysis on the World Wide Web.” In Proceedings
of the 16th ACM Conference on Hypertext and Hypermedia, 1–3. Association for
Computing Machinery, 2005. https://doi.org/10.1145/1083356.1083357.
ieee: M. H. Henzinger, “Hyperlink analysis on the world wide web,” in Proceedings
of the 16th ACM conference on Hypertext and hypermedia, Salzburg, Austria,
2005, pp. 1–3.
ista: 'Henzinger MH. 2005. Hyperlink analysis on the world wide web. Proceedings
of the 16th ACM conference on Hypertext and hypermedia. HYPERTEXT: Conference
on Hypertext and Hypermedia, 1–3.'
mla: Henzinger, Monika H. “Hyperlink Analysis on the World Wide Web.” Proceedings
of the 16th ACM Conference on Hypertext and Hypermedia, Association for Computing
Machinery, 2005, pp. 1–3, doi:10.1145/1083356.1083357.
short: M.H. Henzinger, in:, Proceedings of the 16th ACM Conference on Hypertext
and Hypermedia, Association for Computing Machinery, 2005, pp. 1–3.
conference:
end_date: 2005-09-09
location: Salzburg, Austria
name: 'HYPERTEXT: Conference on Hypertext and Hypermedia'
start_date: 2005-09-06
date_created: 2022-07-29T10:47:23Z
date_published: 2005-09-06T00:00:00Z
date_updated: 2023-02-09T11:54:40Z
day: '06'
doi: 10.1145/1083356.1083357
extern: '1'
keyword:
- Hyperlink Analysis
- World Wide Web
language:
- iso: eng
month: '09'
oa_version: None
page: 1-3
publication: Proceedings of the 16th ACM conference on Hypertext and hypermedia
publication_identifier:
isbn:
- '9781595931689'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Hyperlink analysis on the world wide web
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2005'
...
---
_id: '11763'
abstract:
- lang: eng
text: "We present the first polylog-competitive online algorithm for the general
multicast admission control and routing problem in the throughput model. The ratio
of the number of requests accepted by the optimum offline algorithm to the expected
number of requests accepted by our algorithm is O((log n + log log M)(log n +
log M) log n), where M is the number of multicast groups and n is the number of
nodes in the graph. We show that this is close to optimum by presenting an\r\nΩ(log
n log M) lower bound on this ratio for any randomized online algorithm against
an oblivious adversary, when M is much larger than the link capacities. Our lower
bound applies even in the restricted case where the link capacities are much larger
than bandwidth requested by a single multicast. We also present a simple proof
showing that it is impossible to be competitive against an adaptive online adversary.\r\nAs
in the previous online routing algorithms, our algorithm uses edge-costs when
deciding on which is the best path to use. In contrast to the previous competitive
algorithms in the throughput model, our cost is not a direct function of the edge
load. The new cost definition allows us to decouple the effects of routing and
admission decisions of different multicast groups."
article_processing_charge: No
article_type: original
author:
- first_name: Ashish
full_name: Goel, Ashish
last_name: Goel
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Serge
full_name: Plotkin, Serge
last_name: Plotkin
citation:
ama: Goel A, Henzinger MH, Plotkin S. An online throughput-competitive algorithm
for multicast routing and admission control. Journal of Algorithms. 2005;55(1):1-20.
doi:10.1016/j.jalgor.2004.11.001
apa: Goel, A., Henzinger, M. H., & Plotkin, S. (2005). An online throughput-competitive
algorithm for multicast routing and admission control. Journal of Algorithms.
Elsevier. https://doi.org/10.1016/j.jalgor.2004.11.001
chicago: Goel, Ashish, Monika H Henzinger, and Serge Plotkin. “An Online Throughput-Competitive
Algorithm for Multicast Routing and Admission Control.” Journal of Algorithms.
Elsevier, 2005. https://doi.org/10.1016/j.jalgor.2004.11.001.
ieee: A. Goel, M. H. Henzinger, and S. Plotkin, “An online throughput-competitive
algorithm for multicast routing and admission control,” Journal of Algorithms,
vol. 55, no. 1. Elsevier, pp. 1–20, 2005.
ista: Goel A, Henzinger MH, Plotkin S. 2005. An online throughput-competitive algorithm
for multicast routing and admission control. Journal of Algorithms. 55(1), 1–20.
mla: Goel, Ashish, et al. “An Online Throughput-Competitive Algorithm for Multicast
Routing and Admission Control.” Journal of Algorithms, vol. 55, no. 1,
Elsevier, 2005, pp. 1–20, doi:10.1016/j.jalgor.2004.11.001.
short: A. Goel, M.H. Henzinger, S. Plotkin, Journal of Algorithms 55 (2005) 1–20.
date_created: 2022-08-08T12:03:00Z
date_published: 2005-04-01T00:00:00Z
date_updated: 2023-02-21T16:33:22Z
day: '01'
doi: 10.1016/j.jalgor.2004.11.001
extern: '1'
intvolume: ' 55'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1016/j.jalgor.2004.11.001
month: '04'
oa: 1
oa_version: Published Version
page: 1-20
publication: Journal of Algorithms
publication_identifier:
issn:
- 0196-6774
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
record:
- id: '11926'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: An online throughput-competitive algorithm for multicast routing and admission
control
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 55
year: '2005'
...
---
_id: '8028'
abstract:
- lang: eng
text: 'Transmission of signals within the brain is essential for cognitive function,
but it is not clear how neural circuits support reliable and accurate signal propagation
over a sufficiently large dynamic range. Two modes of propagation have been studied:
synfire chains, in which synchronous activity travels through feedforward layers
of a neuronal network, and the propagation of fluctuations in firing rate across
these layers. In both cases, a sufficient amount of noise, which was added to
previous models from an external source, had to be included to support stable
propagation. Sparse, randomly connected networks of spiking model neurons can
generate chaotic patterns of activity. We investigate whether this activity, which
is a more realistic noise source, is sufficient to allow for signal transmission.
We find that, for rate-coded signals but not for synfire chains, such networks
support robust and accurate signal reproduction through up to six layers if appropriate
adjustments are made in synaptic strengths. We investigate the factors affecting
transmission and show that multiple signals can propagate simultaneously along
different pathways. Using this feature, we show how different types of logic gates
can arise within the architecture of the random network through the strengthening
of specific synapses.'
article_processing_charge: No
article_type: original
author:
- first_name: Tim P
full_name: Vogels, Tim P
id: CB6FF8D2-008F-11EA-8E08-2637E6697425
last_name: Vogels
orcid: 0000-0003-3295-6181
- first_name: L. F.
full_name: Abbott, L. F.
last_name: Abbott
citation:
ama: Vogels TP, Abbott LF. Signal propagation and logic gating in networks of integrate-and-fire
neurons. Journal of Neuroscience. 2005;25(46):10786-10795. doi:10.1523/jneurosci.3508-05.2005
apa: Vogels, T. P., & Abbott, L. F. (2005). Signal propagation and logic gating
in networks of integrate-and-fire neurons. Journal of Neuroscience. Society
for Neuroscience. https://doi.org/10.1523/jneurosci.3508-05.2005
chicago: Vogels, Tim P, and L. F. Abbott. “Signal Propagation and Logic Gating in
Networks of Integrate-and-Fire Neurons.” Journal of Neuroscience. Society
for Neuroscience, 2005. https://doi.org/10.1523/jneurosci.3508-05.2005.
ieee: T. P. Vogels and L. F. Abbott, “Signal propagation and logic gating in networks
of integrate-and-fire neurons,” Journal of Neuroscience, vol. 25, no. 46.
Society for Neuroscience, pp. 10786–10795, 2005.
ista: Vogels TP, Abbott LF. 2005. Signal propagation and logic gating in networks
of integrate-and-fire neurons. Journal of Neuroscience. 25(46), 10786–10795.
mla: Vogels, Tim P., and L. F. Abbott. “Signal Propagation and Logic Gating in Networks
of Integrate-and-Fire Neurons.” Journal of Neuroscience, vol. 25, no. 46,
Society for Neuroscience, 2005, pp. 10786–95, doi:10.1523/jneurosci.3508-05.2005.
short: T.P. Vogels, L.F. Abbott, Journal of Neuroscience 25 (2005) 10786–10795.
date_created: 2020-06-25T13:12:33Z
date_published: 2005-11-16T00:00:00Z
date_updated: 2021-01-12T08:16:37Z
day: '16'
doi: 10.1523/jneurosci.3508-05.2005
extern: '1'
external_id:
pmid:
- '16291952'
intvolume: ' 25'
issue: '46'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6725859/
month: '11'
oa: 1
oa_version: Published Version
page: 10786-10795
pmid: 1
publication: Journal of Neuroscience
publication_identifier:
issn:
- 0270-6474
- 1529-2401
publication_status: published
publisher: Society for Neuroscience
quality_controlled: '1'
status: public
title: Signal propagation and logic gating in networks of integrate-and-fire neurons
type: journal_article
user_id: D865714E-FA4E-11E9-B85B-F5C5E5697425
volume: 25
year: '2005'
...
---
_id: '8029'
abstract:
- lang: eng
text: 'Neural network modeling is often concerned with stimulus-driven responses,
but most of the activity in the brain is internally generated. Here, we review
network models of internally generated activity, focusing on three types of network
dynamics: (a) sustained responses to transient stimuli, which provide a model
of working memory; (b) oscillatory network activity; and (c) chaotic activity,
which models complex patterns of background spiking in cortical and other circuits.
We also review propagation of stimulus-driven activity through spontaneously active
networks. Exploring these aspects of neural network dynamics is critical for understanding
how neural circuits produce cognitive function.'
article_processing_charge: No
article_type: review
author:
- first_name: Tim P
full_name: Vogels, Tim P
id: CB6FF8D2-008F-11EA-8E08-2637E6697425
last_name: Vogels
orcid: 0000-0003-3295-6181
- first_name: Kanaka
full_name: Rajan, Kanaka
last_name: Rajan
- first_name: L.F.
full_name: Abbott, L.F.
last_name: Abbott
citation:
ama: Vogels TP, Rajan K, Abbott LF. Neural network dynamics. Annual Review of
Neuroscience. 2005;28(1):357-376. doi:10.1146/annurev.neuro.28.061604.135637
apa: Vogels, T. P., Rajan, K., & Abbott, L. F. (2005). Neural network dynamics.
Annual Review of Neuroscience. Annual Reviews. https://doi.org/10.1146/annurev.neuro.28.061604.135637
chicago: Vogels, Tim P, Kanaka Rajan, and L.F. Abbott. “Neural Network Dynamics.”
Annual Review of Neuroscience. Annual Reviews, 2005. https://doi.org/10.1146/annurev.neuro.28.061604.135637.
ieee: T. P. Vogels, K. Rajan, and L. F. Abbott, “Neural network dynamics,” Annual
Review of Neuroscience, vol. 28, no. 1. Annual Reviews, pp. 357–376, 2005.
ista: Vogels TP, Rajan K, Abbott LF. 2005. Neural network dynamics. Annual Review
of Neuroscience. 28(1), 357–376.
mla: Vogels, Tim P., et al. “Neural Network Dynamics.” Annual Review of Neuroscience,
vol. 28, no. 1, Annual Reviews, 2005, pp. 357–76, doi:10.1146/annurev.neuro.28.061604.135637.
short: T.P. Vogels, K. Rajan, L.F. Abbott, Annual Review of Neuroscience 28 (2005)
357–376.
date_created: 2020-06-25T13:13:11Z
date_published: 2005-07-21T00:00:00Z
date_updated: 2021-01-12T08:16:37Z
day: '21'
doi: 10.1146/annurev.neuro.28.061604.135637
extern: '1'
external_id:
pmid:
- '16022600'
intvolume: ' 28'
issue: '1'
language:
- iso: eng
month: '07'
oa_version: None
page: 357-376
pmid: 1
publication: Annual Review of Neuroscience
publication_identifier:
issn:
- 0147-006X
- 1545-4126
publication_status: published
publisher: Annual Reviews
quality_controlled: '1'
status: public
title: Neural network dynamics
type: journal_article
user_id: D865714E-FA4E-11E9-B85B-F5C5E5697425
volume: 28
year: '2005'
...
---
_id: '843'
abstract:
- lang: eng
text: The impact of an amino acid replacement on the organism's fitness can vary
from lethal to selectively neutral and even, in rare cases, beneficial. Substantial
data are available on either pathogenic or acceptable replacements. However, the
whole distribution of coefficients of selection against individual replacements
is not known for any organism. To ascertain this distribution for human proteins,
we combined data on pathogenic missense mutations, on human non-synonymous SNPs
and on human-chimpanzee divergence of orthologous proteins. Fractions of amino
acid replacements which reduce fitness by >10-2, 10-2-10-4, 10-4-10-5 and <10-5
are 25, 49, 14 and 12%, respectively. On average, the strength of selection against
a replacement is substantially higher when chemically dissimilar amino acids are
involved, and the Grantham's index of a replacement explains 35% of variance in
the average logarithm of selection coefficients associated with different replacements.
Still, the impact of a replacement depends on its context within the protein more
than on its own nature. Reciprocal replacements are often associated with rather
different selection coefficients, in particular, replacements of non-polar amino
acids with polar ones are typically much more deleterious than replacements in
the opposite direction. However, differences between evolutionary fluxes of reciprocal
replacements are only weakly correlated with the differences between the corresponding
selection coefficients.
author:
- first_name: Lev
full_name: Yampolsky, Lev Y
last_name: Yampolsky
- first_name: Fyodor
full_name: Fyodor Kondrashov
id: 44FDEF62-F248-11E8-B48F-1D18A9856A87
last_name: Kondrashov
orcid: 0000-0001-8243-4694
- first_name: Alexey
full_name: Kondrashov, Alexey S
last_name: Kondrashov
citation:
ama: Yampolsky L, Kondrashov F, Kondrashov A. Distribution of the strength of selection
against amino acid replacements in human proteins. Human Molecular Genetics.
2005;14(21):3191-3201. doi:10.1093/hmg/ddi350
apa: Yampolsky, L., Kondrashov, F., & Kondrashov, A. (2005). Distribution of
the strength of selection against amino acid replacements in human proteins. Human
Molecular Genetics. Oxford University Press. https://doi.org/10.1093/hmg/ddi350
chicago: Yampolsky, Lev, Fyodor Kondrashov, and Alexey Kondrashov. “Distribution
of the Strength of Selection against Amino Acid Replacements in Human Proteins.”
Human Molecular Genetics. Oxford University Press, 2005. https://doi.org/10.1093/hmg/ddi350.
ieee: L. Yampolsky, F. Kondrashov, and A. Kondrashov, “Distribution of the strength
of selection against amino acid replacements in human proteins,” Human Molecular
Genetics, vol. 14, no. 21. Oxford University Press, pp. 3191–3201, 2005.
ista: Yampolsky L, Kondrashov F, Kondrashov A. 2005. Distribution of the strength
of selection against amino acid replacements in human proteins. Human Molecular
Genetics. 14(21), 3191–3201.
mla: Yampolsky, Lev, et al. “Distribution of the Strength of Selection against Amino
Acid Replacements in Human Proteins.” Human Molecular Genetics, vol. 14,
no. 21, Oxford University Press, 2005, pp. 3191–201, doi:10.1093/hmg/ddi350.
short: L. Yampolsky, F. Kondrashov, A. Kondrashov, Human Molecular Genetics 14 (2005)
3191–3201.
date_created: 2018-12-11T11:48:48Z
date_published: 2005-11-01T00:00:00Z
date_updated: 2021-01-12T08:19:13Z
day: '01'
doi: 10.1093/hmg/ddi350
extern: 1
intvolume: ' 14'
issue: '21'
month: '11'
page: 3191 - 3201
publication: Human Molecular Genetics
publication_status: published
publisher: Oxford University Press
publist_id: '6807'
quality_controlled: 0
status: public
title: Distribution of the strength of selection against amino acid replacements in
human proteins
type: journal_article
volume: 14
year: '2005'
...
---
_id: '8491'
abstract:
- lang: eng
text: Fast multidimensional NMR with a time resolution of a few seconds provides
a new tool for high throughput screening and site-resolved real-time studies of
kinetic molecular processes by NMR. Recently we have demonstrated the feasibility
to record protein 1H–15N correlation spectra in a few seconds of acquisition time
using a new SOFAST-HMQC experiment (Schanda and Brutscher (2005) J. Am. Chem.
Soc. 127, 8014). Here, we investigate in detail the performance of SOFAST-HMQC
to record 1H–15N and 1H−13C correlation spectra of proteins of different size
and at different magnetic field strengths. Compared to standard 1H–15N correlation
experiments SOFAST-HMQC provides a significant gain in sensitivity, especially
for fast repetition rates. Guidelines are provided on how to set up SOFAST-HMQC
experiments for a given protein sample. In addition, an alternative pulse scheme,
IPAP-SOFAST-HMQC is presented that allows application on NMR spectrometers equipped
with cryogenic probes, and fast measurement of one-bond 1H–13C and 1H–15N scalar
and residual dipolar coupling constants.
article_processing_charge: No
article_type: original
author:
- first_name: Paul
full_name: Schanda, Paul
id: 7B541462-FAF6-11E9-A490-E8DFE5697425
last_name: Schanda
orcid: 0000-0002-9350-7606
- first_name: Ēriks
full_name: Kupče, Ēriks
last_name: Kupče
- first_name: Bernhard
full_name: Brutscher, Bernhard
last_name: Brutscher
citation:
ama: Schanda P, Kupče Ē, Brutscher B. SOFAST-HMQC experiments for recording two-dimensional
deteronuclear correlation spectra of proteins within a few seconds. Journal
of Biomolecular NMR. 2005;33(4):199-211. doi:10.1007/s10858-005-4425-x
apa: Schanda, P., Kupče, Ē., & Brutscher, B. (2005). SOFAST-HMQC experiments
for recording two-dimensional deteronuclear correlation spectra of proteins within
a few seconds. Journal of Biomolecular NMR. Springer Nature. https://doi.org/10.1007/s10858-005-4425-x
chicago: Schanda, Paul, Ēriks Kupče, and Bernhard Brutscher. “SOFAST-HMQC Experiments
for Recording Two-Dimensional Deteronuclear Correlation Spectra of Proteins within
a Few Seconds.” Journal of Biomolecular NMR. Springer Nature, 2005. https://doi.org/10.1007/s10858-005-4425-x.
ieee: P. Schanda, Ē. Kupče, and B. Brutscher, “SOFAST-HMQC experiments for recording
two-dimensional deteronuclear correlation spectra of proteins within a few seconds,”
Journal of Biomolecular NMR, vol. 33, no. 4. Springer Nature, pp. 199–211,
2005.
ista: Schanda P, Kupče Ē, Brutscher B. 2005. SOFAST-HMQC experiments for recording
two-dimensional deteronuclear correlation spectra of proteins within a few seconds.
Journal of Biomolecular NMR. 33(4), 199–211.
mla: Schanda, Paul, et al. “SOFAST-HMQC Experiments for Recording Two-Dimensional
Deteronuclear Correlation Spectra of Proteins within a Few Seconds.” Journal
of Biomolecular NMR, vol. 33, no. 4, Springer Nature, 2005, pp. 199–211, doi:10.1007/s10858-005-4425-x.
short: P. Schanda, Ē. Kupče, B. Brutscher, Journal of Biomolecular NMR 33 (2005)
199–211.
date_created: 2020-09-18T10:13:59Z
date_published: 2005-12-01T00:00:00Z
date_updated: 2021-01-12T08:19:38Z
day: '01'
doi: 10.1007/s10858-005-4425-x
extern: '1'
intvolume: ' 33'
issue: '4'
keyword:
- Spectroscopy
- Biochemistry
language:
- iso: eng
month: '12'
oa_version: None
page: 199-211
publication: Journal of Biomolecular NMR
publication_identifier:
issn:
- 0925-2738
- 1573-5001
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: SOFAST-HMQC experiments for recording two-dimensional deteronuclear correlation
spectra of proteins within a few seconds
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 33
year: '2005'
...
---
_id: '8492'
abstract:
- lang: eng
text: We demonstrate for different protein samples that 2D 1H−15N correlation NMR
spectra can be recorded in a few seconds of acquisition time using a new band-selective
optimized flip-angle short-transient heteronuclear multiple quantum coherence
experiment. This has enabled us to measure fast hydrogen−deuterium exchange rate
constants along the backbone of a small globular protein fragment by real-time
2D NMR.
article_processing_charge: No
article_type: original
author:
- first_name: Paul
full_name: Schanda, Paul
id: 7B541462-FAF6-11E9-A490-E8DFE5697425
last_name: Schanda
orcid: 0000-0002-9350-7606
- first_name: Bernhard
full_name: Brutscher, Bernhard
last_name: Brutscher
citation:
ama: Schanda P, Brutscher B. Very fast two-dimensional NMR spectroscopy for real-time
investigation of dynamic events in proteins on the time scale of seconds. Journal
of the American Chemical Society. 2005;127(22):8014-8015. doi:10.1021/ja051306e
apa: Schanda, P., & Brutscher, B. (2005). Very fast two-dimensional NMR spectroscopy
for real-time investigation of dynamic events in proteins on the time scale of
seconds. Journal of the American Chemical Society. American Chemical Society.
https://doi.org/10.1021/ja051306e
chicago: Schanda, Paul, and Bernhard Brutscher. “Very Fast Two-Dimensional NMR Spectroscopy
for Real-Time Investigation of Dynamic Events in Proteins on the Time Scale of
Seconds.” Journal of the American Chemical Society. American Chemical Society,
2005. https://doi.org/10.1021/ja051306e.
ieee: P. Schanda and B. Brutscher, “Very fast two-dimensional NMR spectroscopy for
real-time investigation of dynamic events in proteins on the time scale of seconds,”
Journal of the American Chemical Society, vol. 127, no. 22. American Chemical
Society, pp. 8014–8015, 2005.
ista: Schanda P, Brutscher B. 2005. Very fast two-dimensional NMR spectroscopy for
real-time investigation of dynamic events in proteins on the time scale of seconds.
Journal of the American Chemical Society. 127(22), 8014–8015.
mla: Schanda, Paul, and Bernhard Brutscher. “Very Fast Two-Dimensional NMR Spectroscopy
for Real-Time Investigation of Dynamic Events in Proteins on the Time Scale of
Seconds.” Journal of the American Chemical Society, vol. 127, no. 22, American
Chemical Society, 2005, pp. 8014–15, doi:10.1021/ja051306e.
short: P. Schanda, B. Brutscher, Journal of the American Chemical Society 127 (2005)
8014–8015.
date_created: 2020-09-18T10:14:05Z
date_published: 2005-05-14T00:00:00Z
date_updated: 2021-01-12T08:19:39Z
day: '14'
doi: 10.1021/ja051306e
extern: '1'
intvolume: ' 127'
issue: '22'
keyword:
- Colloid and Surface Chemistry
- Biochemistry
- General Chemistry
- Catalysis
language:
- iso: eng
month: '05'
oa_version: None
page: 8014-8015
publication: Journal of the American Chemical Society
publication_identifier:
issn:
- 0002-7863
- 1520-5126
publication_status: published
publisher: American Chemical Society
quality_controlled: '1'
status: public
title: Very fast two-dimensional NMR spectroscopy for real-time investigation of dynamic
events in proteins on the time scale of seconds
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 127
year: '2005'
...
---
_id: '8516'
abstract:
- lang: eng
text: "The purpose of this paper is to construct examples of diffusion for E-Hamiltonian
perturbations\r\nof completely integrable Hamiltonian systems in 2d-dimensional
phase space, with d large.\r\nIn the first part of the paper, simple and explicit
examples are constructed illustrating absence\r\nof ‘long-time’ stability for
size E Hamiltonian perturbations of quasi-convex integrable systems\r\nalready
when the dimension 2d of phase space becomes as large as log 1/E . We first produce\r\nthe
example in Gevrey class and then a real analytic one, with some additional work.\r\nIn
the second part, we consider again E-Hamiltonian perturbations of completely integrable\r\nHamiltonian
system in 2d-dimensional space with E-small but not too small, |E| > exp(−d),
with\r\nd the number of degrees of freedom assumed large. It is shown that for
a class of analytic\r\ntime-periodic perturbations, there exist linearly diffusing
trajectories. The underlying idea for\r\nboth examples is similar and consists
in coupling a fixed degree of freedom with a large\r\nnumber of them. The procedure
and analytical details are however significantly different. As\r\nmentioned, the
construction in Part I is totally elementary while Part II is more involved, relying\r\nin
particular on the theory of normally hyperbolic invariant manifolds, methods of
generating\r\nfunctions, Aubry–Mather theory, and Mather’s variational methods."
article_processing_charge: No
article_type: original
author:
- first_name: Jean
full_name: Bourgain, Jean
last_name: Bourgain
- first_name: Vadim
full_name: Kaloshin, Vadim
id: FE553552-CDE8-11E9-B324-C0EBE5697425
last_name: Kaloshin
orcid: 0000-0002-6051-2628
citation:
ama: Bourgain J, Kaloshin V. On diffusion in high-dimensional Hamiltonian systems.
Journal of Functional Analysis. 2005;229(1):1-61. doi:10.1016/j.jfa.2004.09.006
apa: Bourgain, J., & Kaloshin, V. (2005). On diffusion in high-dimensional Hamiltonian
systems. Journal of Functional Analysis. Elsevier. https://doi.org/10.1016/j.jfa.2004.09.006
chicago: Bourgain, Jean, and Vadim Kaloshin. “On Diffusion in High-Dimensional Hamiltonian
Systems.” Journal of Functional Analysis. Elsevier, 2005. https://doi.org/10.1016/j.jfa.2004.09.006.
ieee: J. Bourgain and V. Kaloshin, “On diffusion in high-dimensional Hamiltonian
systems,” Journal of Functional Analysis, vol. 229, no. 1. Elsevier, pp.
1–61, 2005.
ista: Bourgain J, Kaloshin V. 2005. On diffusion in high-dimensional Hamiltonian
systems. Journal of Functional Analysis. 229(1), 1–61.
mla: Bourgain, Jean, and Vadim Kaloshin. “On Diffusion in High-Dimensional Hamiltonian
Systems.” Journal of Functional Analysis, vol. 229, no. 1, Elsevier, 2005,
pp. 1–61, doi:10.1016/j.jfa.2004.09.006.
short: J. Bourgain, V. Kaloshin, Journal of Functional Analysis 229 (2005) 1–61.
date_created: 2020-09-18T10:49:06Z
date_published: 2005-12-01T00:00:00Z
date_updated: 2021-01-12T08:19:49Z
day: '01'
doi: 10.1016/j.jfa.2004.09.006
extern: '1'
intvolume: ' 229'
issue: '1'
keyword:
- Analysis
language:
- iso: eng
month: '12'
oa_version: None
page: 1-61
publication: Journal of Functional Analysis
publication_identifier:
issn:
- 0022-1236
publication_status: published
publisher: Elsevier
quality_controlled: '1'
status: public
title: On diffusion in high-dimensional Hamiltonian systems
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 229
year: '2005'
...
---
_id: '877'
abstract:
- lang: eng
text: "Sequence analysis of protein and mitochondrially encoded tRNA genes shows
that substitutions\r\nproducing pathogenic effects in humans are often found in
normal, healthy individuals from other species.\r\nAnalysis of stability of protein
and tRNA structures shows that the disease-causing effects of pathogenic\r\nmutations
can be neutralized by other, compensatory substitutions that restore the structural
stability of the\r\nmolecule. Further study of such substitutions will, hopefully,
lead to new methods for curing genetic dis-\r\neases that may be based on the
correction of molecule stability as a whole instead of reversing an individual\r\npathogenic
mutation."
article_processing_charge: No
article_type: original
author:
- first_name: Fyodor
full_name: Kondrashov, Fyodor
id: 44FDEF62-F248-11E8-B48F-1D18A9856A87
last_name: Kondrashov
orcid: 0000-0001-8243-4694
citation:
ama: Kondrashov F. The analysis of monomer sequences in protein and tRNA and the
manifestation of the compensation of pathogenic deviations in their evolution.
Biofizika. 2005;50(3):389-395.
apa: Kondrashov, F. (2005). The analysis of monomer sequences in protein and tRNA
and the manifestation of the compensation of pathogenic deviations in their evolution.
Biofizika. Pleiades Publishing.
chicago: Kondrashov, Fyodor. “The Analysis of Monomer Sequences in Protein and TRNA
and the Manifestation of the Compensation of Pathogenic Deviations in Their Evolution.”
Biofizika. Pleiades Publishing, 2005.
ieee: F. Kondrashov, “The analysis of monomer sequences in protein and tRNA and
the manifestation of the compensation of pathogenic deviations in their evolution,”
Biofizika, vol. 50, no. 3. Pleiades Publishing, pp. 389–395, 2005.
ista: Kondrashov F. 2005. The analysis of monomer sequences in protein and tRNA
and the manifestation of the compensation of pathogenic deviations in their evolution.
Biofizika. 50(3), 389–395.
mla: Kondrashov, Fyodor. “The Analysis of Monomer Sequences in Protein and TRNA
and the Manifestation of the Compensation of Pathogenic Deviations in Their Evolution.”
Biofizika, vol. 50, no. 3, Pleiades Publishing, 2005, pp. 389–95.
short: F. Kondrashov, Biofizika 50 (2005) 389–395.
date_created: 2018-12-11T11:48:58Z
date_published: 2005-05-01T00:00:00Z
date_updated: 2021-01-12T08:21:01Z
day: '01'
extern: '1'
external_id:
pmid:
- '15977826'
intvolume: ' 50'
issue: '3'
language:
- iso: eng
main_file_link:
- url: http://pleiades.online/abstract/biophys/5/biophys0349_abstract.pdf
month: '05'
oa_version: None
page: 389 - 395
pmid: 1
publication: Biofizika
publication_status: published
publisher: Pleiades Publishing
publist_id: '6769'
quality_controlled: '1'
status: public
title: The analysis of monomer sequences in protein and tRNA and the manifestation
of the compensation of pathogenic deviations in their evolution
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 50
year: '2005'
...
---
_id: '878'
abstract:
- lang: eng
text: |
Negative trade-offs are thought to be a pervasive phenomenon and to inhibit evolution at all levels. New evidence shows that at the molecular level, there may be no trade-offs preventing the emergence of an enzyme with multiple functions.
author:
- first_name: Fyodor
full_name: Fyodor Kondrashov
id: 44FDEF62-F248-11E8-B48F-1D18A9856A87
last_name: Kondrashov
orcid: 0000-0001-8243-4694
citation:
ama: Kondrashov F. In search of the limits of evolution. Nature Genetics.
2005;37(1):9-10. doi:10.1038/ng0105-9
apa: Kondrashov, F. (2005). In search of the limits of evolution. Nature Genetics.
Nature Publishing Group. https://doi.org/10.1038/ng0105-9
chicago: Kondrashov, Fyodor. “In Search of the Limits of Evolution.” Nature Genetics.
Nature Publishing Group, 2005. https://doi.org/10.1038/ng0105-9.
ieee: F. Kondrashov, “In search of the limits of evolution,” Nature Genetics,
vol. 37, no. 1. Nature Publishing Group, pp. 9–10, 2005.
ista: Kondrashov F. 2005. In search of the limits of evolution. Nature Genetics.
37(1), 9–10.
mla: Kondrashov, Fyodor. “In Search of the Limits of Evolution.” Nature Genetics,
vol. 37, no. 1, Nature Publishing Group, 2005, pp. 9–10, doi:10.1038/ng0105-9.
short: F. Kondrashov, Nature Genetics 37 (2005) 9–10.
date_created: 2018-12-11T11:48:59Z
date_published: 2005-01-01T00:00:00Z
date_updated: 2021-01-12T08:21:02Z
day: '01'
doi: 10.1038/ng0105-9
extern: 1
intvolume: ' 37'
issue: '1'
month: '01'
page: 9 - 10
publication: Nature Genetics
publication_status: published
publisher: Nature Publishing Group
publist_id: '6770'
quality_controlled: 0
status: public
title: In search of the limits of evolution
type: journal_article
volume: 37
year: '2005'
...
---
_id: '880'
abstract:
- lang: eng
text: Here, I describe a case of loss of the D-arm by mitochondrial cysteine tRNA
in the nine-banded armadillo (Dasypus novemcinctus) convergent with mt tRNASer(AGY).
Such evolution sheds light on the relationship between structure and function
of tRNA molecules and its impact on the patterns of molecular evolution.
article_processing_charge: No
author:
- first_name: Fyodor
full_name: Kondrashov, Fyodor
id: 44FDEF62-F248-11E8-B48F-1D18A9856A87
last_name: Kondrashov
orcid: 0000-0001-8243-4694
citation:
ama: Kondrashov F. The convergent evolution of the secondary structure of mitochondrial
cysteine tRNA in the nine-banded armadillo Dasypus novemcinctus. Biofizika.
2005;50(3):396-403.
apa: Kondrashov, F. (2005). The convergent evolution of the secondary structure
of mitochondrial cysteine tRNA in the nine-banded armadillo Dasypus novemcinctus.
Biofizika. Pleiades Publishing.
chicago: Kondrashov, Fyodor. “The Convergent Evolution of the Secondary Structure
of Mitochondrial Cysteine TRNA in the Nine-Banded Armadillo Dasypus Novemcinctus.”
Biofizika. Pleiades Publishing, 2005.
ieee: F. Kondrashov, “The convergent evolution of the secondary structure of mitochondrial
cysteine tRNA in the nine-banded armadillo Dasypus novemcinctus,” Biofizika,
vol. 50, no. 3. Pleiades Publishing, pp. 396–403, 2005.
ista: Kondrashov F. 2005. The convergent evolution of the secondary structure of
mitochondrial cysteine tRNA in the nine-banded armadillo Dasypus novemcinctus.
Biofizika. 50(3), 396–403.
mla: Kondrashov, Fyodor. “The Convergent Evolution of the Secondary Structure of
Mitochondrial Cysteine TRNA in the Nine-Banded Armadillo Dasypus Novemcinctus.”
Biofizika, vol. 50, no. 3, Pleiades Publishing, 2005, pp. 396–403.
short: F. Kondrashov, Biofizika 50 (2005) 396–403.
date_created: 2018-12-11T11:48:59Z
date_published: 2005-05-01T00:00:00Z
date_updated: 2021-01-12T08:21:07Z
day: '01'
extern: '1'
external_id:
pmid:
- '15977827'
intvolume: ' 50'
issue: '3'
language:
- iso: eng
main_file_link:
- url: http://pleiades.online/abstract/biophys/5/biophys0356_abstract.pdf
month: '05'
oa_version: None
page: 396 - 403
pmid: 1
publication: Biofizika
publication_status: published
publisher: Pleiades Publishing
publist_id: '6768'
quality_controlled: '1'
status: public
title: The convergent evolution of the secondary structure of mitochondrial cysteine
tRNA in the nine-banded armadillo Dasypus novemcinctus
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 50
year: '2005'
...