---
_id: '3166'
abstract:
- lang: eng
text: 'There is evidence that the genetic code was established prior to the existence
of proteins, when metabolism was powered by ribozymes. Also, early proto-organisms
had to rely on simple anaerobic bioenergetic processes. In this work I propose
that amino acid fermentation powered metabolism in the RNA world, and that this
was facilitated by proto-adapters, the precursors of the tRNAs. Amino acids were
used as carbon sources rather than as catalytic or structural elements. In modern
bacteria, amino acid fermentation is known as the Stickland reaction. This pathway
involves two amino acids: the first undergoes oxidative deamination, and the second
acts as an electron acceptor through reductive deamination. This redox reaction
results in two keto acids that are employed to synthesise ATP via substrate-level
phosphorylation. The Stickland reaction is the basic bioenergetic pathway of some
bacteria of the genus Clostridium. Two other facts support Stickland fermentation
in the RNA world. First, several Stickland amino acid pairs are synthesised in
abiotic amino acid synthesis. This suggests that amino acids that could be used
as an energy substrate were freely available. Second, anticodons that have complementary
sequences often correspond to amino acids that form Stickland pairs. The main
hypothesis of this paper is that pairs of complementary proto-adapters were assigned
to Stickland amino acids pairs. There are signatures of this hypothesis in the
genetic code. Furthermore, it is argued that the proto-adapters formed double
strands that brought amino acid pairs into proximity to facilitate their mutual
redox reaction, structurally constraining the anticodon pairs that are assigned
to these amino acid pairs. Significance tests which randomise the code are performed
to study the extent of the variability of the energetic (ATP) yield. Random assignments
can lead to a substantial yield of ATP and maintain enough variability, thus selection
can act and refine the assignments into a proto-code that optimises the energetic
yield. Monte Carlo simulations are performed to evaluate the establishment of
these simple proto-codes, based on amino acid substitutions and codon swapping.
In all cases, donor amino acids are assigned to anticodons composed of U+G, and
have low redundancy (1-2 codons), whereas acceptor amino acids are assigned to
the the remaining codons. These bioenergetic and structural constraints allow
for a metabolic role for amino acids before their co-option as catalyst cofactors.
Reviewers: this article was reviewed by Prof. William Martin, Prof. Eors Szathmary
(nominated by Dr. Gaspar Jekely) and Dr. Adam Kun (nominated by Dr. Sandor Pongor)'
acknowledgement: 'The author was supported by the ERC-2009-AdG Grant for project 250152
SELECTIONINFORMATION. '
article_number: '6'
article_processing_charge: No
author:
- first_name: Harold
full_name: Vladar, Harold
id: 2A181218-F248-11E8-B48F-1D18A9856A87
last_name: Vladar
orcid: 0000-0002-5985-7653
citation:
ama: de Vladar H. Amino acid fermentation at the origin of the genetic code. Biology
Direct. 2012;7. doi:10.1186/1745-6150-7-6
apa: de Vladar, H. (2012). Amino acid fermentation at the origin of the genetic
code. Biology Direct. BioMed Central. https://doi.org/10.1186/1745-6150-7-6
chicago: Vladar, Harold de. “Amino Acid Fermentation at the Origin of the Genetic
Code.” Biology Direct. BioMed Central, 2012. https://doi.org/10.1186/1745-6150-7-6.
ieee: H. de Vladar, “Amino acid fermentation at the origin of the genetic code,”
Biology Direct, vol. 7. BioMed Central, 2012.
ista: de Vladar H. 2012. Amino acid fermentation at the origin of the genetic code.
Biology Direct. 7, 6.
mla: de Vladar, Harold. “Amino Acid Fermentation at the Origin of the Genetic Code.”
Biology Direct, vol. 7, 6, BioMed Central, 2012, doi:10.1186/1745-6150-7-6.
short: H. de Vladar, Biology Direct 7 (2012).
corr_author: '1'
date_created: 2018-12-11T12:01:46Z
date_published: 2012-02-10T00:00:00Z
date_updated: 2025-09-30T07:51:20Z
day: '10'
ddc:
- '570'
- '576'
department:
- _id: NiBa
doi: 10.1186/1745-6150-7-6
ec_funded: 1
external_id:
isi:
- '000305269300001'
file:
- access_level: open_access
checksum: e511e401e239ef608a7fd79b21a06d78
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:15:44Z
date_updated: 2020-07-14T12:46:02Z
file_id: '5166'
file_name: IST-2012-99-v1+1_1745-6150-7-6.pdf
file_size: 4099536
relation: main_file
file_date_updated: 2020-07-14T12:46:02Z
has_accepted_license: '1'
intvolume: ' 7'
isi: 1
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
project:
- _id: 25B07788-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '250152'
name: Limits to selection in biology and in evolutionary computation
publication: Biology Direct
publication_status: published
publisher: BioMed Central
publist_id: '3518'
pubrep_id: '99'
quality_controlled: '1'
status: public
title: Amino acid fermentation at the origin of the genetic code
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 7
year: '2012'
...
---
OA_type: free access
_id: '3167'
article_processing_charge: No
article_type: letter_note
author:
- first_name: Michele
full_name: Weber, Michele
id: 3A3FC708-F248-11E8-B48F-1D18A9856A87
last_name: Weber
citation:
ama: Weber M. NextGen speaks 13 . Science. 2012;336(6077):32-34. doi:10.1126/science.336.6077.32
apa: Weber, M. (2012). NextGen speaks 13 . Science. American Association
for the Advancement of Science. https://doi.org/10.1126/science.336.6077.32
chicago: Weber, Michele. “NextGen Speaks 13 .” Science. American Association
for the Advancement of Science, 2012. https://doi.org/10.1126/science.336.6077.32.
ieee: M. Weber, “NextGen speaks 13 ,” Science, vol. 336, no. 6077. American
Association for the Advancement of Science, pp. 32–34, 2012.
ista: Weber M. 2012. NextGen speaks 13 . Science. 336(6077), 32–34.
mla: Weber, Michele. “NextGen Speaks 13 .” Science, vol. 336, no. 6077, American
Association for the Advancement of Science, 2012, pp. 32–34, doi:10.1126/science.336.6077.32.
short: M. Weber, Science 336 (2012) 32–34.
date_created: 2018-12-11T12:01:47Z
date_published: 2012-04-06T00:00:00Z
date_updated: 2025-05-20T07:14:51Z
day: '06'
department:
- _id: MiSi
doi: 10.1126/science.336.6077.32
external_id:
pmid:
- '22491839'
intvolume: ' 336'
issue: '6077'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1126/science.336.6077.32
month: '04'
oa: 1
oa_version: None
page: 32-34
pmid: 1
popular_science: '1'
publication: Science
publication_status: published
publisher: American Association for the Advancement of Science
publist_id: '3516'
status: public
title: 'NextGen speaks 13 '
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 336
year: '2012'
...
---
_id: '3242'
abstract:
- lang: eng
text: Due to the omnipresent risk of epidemics, insect societies have evolved sophisticated
disease defences at the individual and colony level. An intriguing yet little
understood phenomenon is that social contact to pathogen-exposed individuals reduces
susceptibility of previously naive nestmates to this pathogen. We tested whether
such social immunisation in Lasius ants against the entomopathogenic fungus Metarhizium
anisopliae is based on active upregulation of the immune system of nestmates following
contact to an infectious individual or passive protection via transfer of immune
effectors among group members—that is, active versus passive immunisation. We
found no evidence for involvement of passive immunisation via transfer of antimicrobials
among colony members. Instead, intensive allogrooming behaviour between naive
and pathogen-exposed ants before fungal conidia firmly attached to their cuticle
suggested passage of the pathogen from the exposed individuals to their nestmates.
By tracing fluorescence-labelled conidia we indeed detected frequent pathogen
transfer to the nestmates, where they caused low-level infections as revealed
by growth of small numbers of fungal colony forming units from their dissected
body content. These infections rarely led to death, but instead promoted an enhanced
ability to inhibit fungal growth and an active upregulation of immune genes involved
in antifungal defences (defensin and prophenoloxidase, PPO). Contrarily, there
was no upregulation of the gene cathepsin L, which is associated with antibacterial
and antiviral defences, and we found no increased antibacterial activity of nestmates
of fungus-exposed ants. This indicates that social immunisation after fungal exposure
is specific, similar to recent findings for individual-level immune priming in
invertebrates. Epidemiological modeling further suggests that active social immunisation
is adaptive, as it leads to faster elimination of the disease and lower death
rates than passive immunisation. Interestingly, humans have also utilised the
protective effect of low-level infections to fight smallpox by intentional transfer
of low pathogen doses (“variolation” or “inoculation”).
acknowledgement: Funding for this project was obtained by the German Research Foundation
DFG (http://www.dfg.de/en/index.jsp) as an Individual Research Grant (CR118/2-1
to SC) and the European Research Council (http://erc.europa.eu/) in form of two
ERC Starting Grants (ERC-2009-StG240371-SocialVaccines to SC and ERC-2010-StG259294-LatentCauses
to FJT). In addition, the Junge Akademie (Young Academy of the Berlin-Brandenburg
Academy of Sciences and Humanities and the National Academy of Sciences Leopoldina
(http://www.diejungeakademie.de/english/index.html) funded this joint Antnet project
of SC and FJT. The funders had no role in study design, data collection and analysis,
decision to publish, or preparation of the manuscript.
article_number: e1001300
article_processing_charge: No
author:
- first_name: Matthias
full_name: Konrad, Matthias
id: 46528076-F248-11E8-B48F-1D18A9856A87
last_name: Konrad
- first_name: Meghan
full_name: Vyleta, Meghan
id: 418901AA-F248-11E8-B48F-1D18A9856A87
last_name: Vyleta
- first_name: Fabian
full_name: Theis, Fabian
last_name: Theis
- first_name: Miriam
full_name: Stock, Miriam
id: 42462816-F248-11E8-B48F-1D18A9856A87
last_name: Stock
- first_name: Simon
full_name: Tragust, Simon
id: 35A7A418-F248-11E8-B48F-1D18A9856A87
last_name: Tragust
- first_name: Martina
full_name: Klatt, Martina
id: E60F29C6-E9AE-11E9-AF6E-D190C7302F38
last_name: Klatt
- first_name: Verena
full_name: Drescher, Verena
last_name: Drescher
- first_name: Carsten
full_name: Marr, Carsten
last_name: Marr
- first_name: Line V
full_name: Ugelvig, Line V
id: 3DC97C8E-F248-11E8-B48F-1D18A9856A87
last_name: Ugelvig
orcid: 0000-0003-1832-8883
- first_name: Sylvia
full_name: Cremer, Sylvia
id: 2F64EC8C-F248-11E8-B48F-1D18A9856A87
last_name: Cremer
orcid: 0000-0002-2193-3868
citation:
ama: Konrad M, Vyleta M, Theis F, et al. Social transfer of pathogenic fungus promotes
active immunisation in ant colonies. PLoS Biology. 2012;10(4). doi:10.1371/journal.pbio.1001300
apa: Konrad, M., Vyleta, M., Theis, F., Stock, M., Tragust, S., Klatt, M., … Cremer,
S. (2012). Social transfer of pathogenic fungus promotes active immunisation in
ant colonies. PLoS Biology. Public Library of Science. https://doi.org/10.1371/journal.pbio.1001300
chicago: Konrad, Matthias, Meghan Vyleta, Fabian Theis, Miriam Stock, Simon Tragust,
Martina Klatt, Verena Drescher, Carsten Marr, Line V Ugelvig, and Sylvia Cremer.
“Social Transfer of Pathogenic Fungus Promotes Active Immunisation in Ant Colonies.”
PLoS Biology. Public Library of Science, 2012. https://doi.org/10.1371/journal.pbio.1001300.
ieee: M. Konrad et al., “Social transfer of pathogenic fungus promotes active
immunisation in ant colonies,” PLoS Biology, vol. 10, no. 4. Public Library
of Science, 2012.
ista: Konrad M, Vyleta M, Theis F, Stock M, Tragust S, Klatt M, Drescher V, Marr
C, Ugelvig LV, Cremer S. 2012. Social transfer of pathogenic fungus promotes active
immunisation in ant colonies. PLoS Biology. 10(4), e1001300.
mla: Konrad, Matthias, et al. “Social Transfer of Pathogenic Fungus Promotes Active
Immunisation in Ant Colonies.” PLoS Biology, vol. 10, no. 4, e1001300,
Public Library of Science, 2012, doi:10.1371/journal.pbio.1001300.
short: M. Konrad, M. Vyleta, F. Theis, M. Stock, S. Tragust, M. Klatt, V. Drescher,
C. Marr, L.V. Ugelvig, S. Cremer, PLoS Biology 10 (2012).
corr_author: '1'
date_created: 2018-12-11T12:02:13Z
date_published: 2012-04-03T00:00:00Z
date_updated: 2025-09-30T07:50:01Z
day: '03'
ddc:
- '570'
- '579'
department:
- _id: SyCr
doi: 10.1371/journal.pbio.1001300
ec_funded: 1
external_id:
isi:
- '000303541800006'
file:
- access_level: open_access
checksum: 4ebacefd9fbab5c68adf829124115fd1
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:08:28Z
date_updated: 2020-07-14T12:46:04Z
file_id: '4689'
file_name: IST-2012-96-v1+1_journal.pbio.1001300.pdf
file_size: 674228
relation: main_file
file_date_updated: 2020-07-14T12:46:04Z
has_accepted_license: '1'
intvolume: ' 10'
isi: 1
issue: '4'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
project:
- _id: 25DAF0B2-B435-11E9-9278-68D0E5697425
grant_number: CR-118/3-1
name: Host-Parasite Coevolution
- _id: 25DC711C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '243071'
name: 'Social Vaccination in Ant Colonies: from Individual Mechanisms to Society
Effects'
- _id: 25E0E184-B435-11E9-9278-68D0E5697425
name: Schnellboot Antnet Junge Akademie
publication: PLoS Biology
publication_status: published
publisher: Public Library of Science
publist_id: '3434'
pubrep_id: '96'
quality_controlled: '1'
related_material:
record:
- id: '9755'
relation: research_data
status: public
scopus_import: '1'
status: public
title: Social transfer of pathogenic fungus promotes active immunisation in ant colonies
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 10
year: '2012'
...
---
_id: '3245'
abstract:
- lang: eng
text: How cells orchestrate their behavior during collective migration is a long-standing
question. Using magnetic tweezers to apply mechanical stimuli to Xenopus mesendoderm
cells, Weber etal. (2012) now reveal, in this issue of Developmental Cell, a cadherin-mediated
mechanosensitive response that promotes cell polarization and movement persistence
during the collective mesendoderm migration in gastrulation.
article_processing_charge: No
author:
- first_name: Martin
full_name: Behrndt, Martin
id: 3ECECA3A-F248-11E8-B48F-1D18A9856A87
last_name: Behrndt
- first_name: Carl-Philipp J
full_name: Heisenberg, Carl-Philipp J
id: 39427864-F248-11E8-B48F-1D18A9856A87
last_name: Heisenberg
orcid: 0000-0002-0912-4566
citation:
ama: Behrndt M, Heisenberg C-PJ. Spurred by resistance mechanosensation in collective
migration. Developmental Cell. 2012;22(1):3-4. doi:10.1016/j.devcel.2011.12.018
apa: Behrndt, M., & Heisenberg, C.-P. J. (2012). Spurred by resistance mechanosensation
in collective migration. Developmental Cell. Cell Press. https://doi.org/10.1016/j.devcel.2011.12.018
chicago: Behrndt, Martin, and Carl-Philipp J Heisenberg. “Spurred by Resistance
Mechanosensation in Collective Migration.” Developmental Cell. Cell Press,
2012. https://doi.org/10.1016/j.devcel.2011.12.018.
ieee: M. Behrndt and C.-P. J. Heisenberg, “Spurred by resistance mechanosensation
in collective migration,” Developmental Cell, vol. 22, no. 1. Cell Press,
pp. 3–4, 2012.
ista: Behrndt M, Heisenberg C-PJ. 2012. Spurred by resistance mechanosensation in
collective migration. Developmental Cell. 22(1), 3–4.
mla: Behrndt, Martin, and Carl-Philipp J. Heisenberg. “Spurred by Resistance Mechanosensation
in Collective Migration.” Developmental Cell, vol. 22, no. 1, Cell Press,
2012, pp. 3–4, doi:10.1016/j.devcel.2011.12.018.
short: M. Behrndt, C.-P.J. Heisenberg, Developmental Cell 22 (2012) 3–4.
corr_author: '1'
date_created: 2018-12-11T12:02:14Z
date_published: 2012-01-17T00:00:00Z
date_updated: 2025-09-30T07:48:41Z
day: '17'
department:
- _id: CaHe
doi: 10.1016/j.devcel.2011.12.018
external_id:
isi:
- '000299365800002'
intvolume: ' 22'
isi: 1
issue: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 3 - 4
publication: Developmental Cell
publication_status: published
publisher: Cell Press
publist_id: '3426'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Spurred by resistance mechanosensation in collective migration
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 22
year: '2012'
...
---
_id: '3247'
abstract:
- lang: eng
text: The Brazilian Merganser is a very rare and threatened species that nowadays
inhabits only a few protected areas and their surroundings in the Brazilian territory.
In order to estimate the remaining genetic diversity and population structure
in this species, two mitochondrial genes were sequenced in 39 individuals belonging
to two populations and in one individual collected in Argentina in 1950. We found
a highly significant divergence between two major remaining populations of Mergus
octosetaceus, which suggests a historical population structure in this species.
Furthermore, two deeply divergent lineages were found in a single location, which
could due to current or historical secondary contact. Based on the available genetic
data, we point out future directions which would contribute to design strategies
for conservation and management of this threatened species.
acknowledgement: "The present study received grants from FAPEMIG, CNPq, Petrobras
Ambiental and Fundação O Boticário de Conservação da Natureza, and followed all
ethical guidelines and legal requirements of Brazil for sampling and studying an
endangered species.\r\nWe thank the Specialist Work Group for the Conservation of
Brazilian Merganser for valuable discussions and opinions on this manuscript. We
also thank all the staff from Instituto Terra Brasilis and Funatura (Vivian S. Braz
and Gislaine Disconzi) for collecting the samples at Serra da Canastra and Chapada
dos Veadeiros, respectively; Dario A. Lijtmaerand and Pablo Tubaro for providing
the samples from Argentina, Bradley C. Livezey for sending copies of his papers,
and Geoff M. Hilton and Paulo de Tarso Z. Antas for useful suggestions that greatly
improved this manuscript."
article_processing_charge: No
author:
- first_name: Sibelle
full_name: Vilaça, Sibelle
last_name: Vilaça
- first_name: Rodrigo A
full_name: Fernandes Redondo, Rodrigo A
id: 409D5C96-F248-11E8-B48F-1D18A9856A87
last_name: Fernandes Redondo
orcid: 0000-0002-5837-2793
- first_name: Lívia
full_name: Lins, Lívia
last_name: Lins
- first_name: Fabrício
full_name: Santos, Fabrício
last_name: Santos
citation:
ama: Vilaça S, Fernandes Redondo RA, Lins L, Santos F. Remaining genetic diversity
in Brazilian Merganser (Mergus octosetaceus). Conservation Genetics. 2012;13(1):293-298.
doi:10.1007/s10592-011-0262-5
apa: Vilaça, S., Fernandes Redondo, R. A., Lins, L., & Santos, F. (2012). Remaining
genetic diversity in Brazilian Merganser (Mergus octosetaceus). Conservation
Genetics. Springer. https://doi.org/10.1007/s10592-011-0262-5
chicago: Vilaça, Sibelle, Rodrigo A Fernandes Redondo, Lívia Lins, and Fabrício
Santos. “Remaining Genetic Diversity in Brazilian Merganser (Mergus Octosetaceus).”
Conservation Genetics. Springer, 2012. https://doi.org/10.1007/s10592-011-0262-5.
ieee: S. Vilaça, R. A. Fernandes Redondo, L. Lins, and F. Santos, “Remaining genetic
diversity in Brazilian Merganser (Mergus octosetaceus),” Conservation Genetics,
vol. 13, no. 1. Springer, pp. 293–298, 2012.
ista: Vilaça S, Fernandes Redondo RA, Lins L, Santos F. 2012. Remaining genetic
diversity in Brazilian Merganser (Mergus octosetaceus). Conservation Genetics.
13(1), 293–298.
mla: Vilaça, Sibelle, et al. “Remaining Genetic Diversity in Brazilian Merganser
(Mergus Octosetaceus).” Conservation Genetics, vol. 13, no. 1, Springer,
2012, pp. 293–98, doi:10.1007/s10592-011-0262-5.
short: S. Vilaça, R.A. Fernandes Redondo, L. Lins, F. Santos, Conservation Genetics
13 (2012) 293–298.
date_created: 2018-12-11T12:02:15Z
date_published: 2012-02-01T00:00:00Z
date_updated: 2025-09-30T07:47:07Z
day: '01'
department:
- _id: JoBo
doi: 10.1007/s10592-011-0262-5
external_id:
isi:
- '000303475800024'
intvolume: ' 13'
isi: 1
issue: '1'
language:
- iso: eng
month: '02'
oa_version: None
page: 293 - 298
publication: Conservation Genetics
publication_status: published
publisher: Springer
publist_id: '3420'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Remaining genetic diversity in Brazilian Merganser (Mergus octosetaceus)
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 13
year: '2012'
...
---
_id: '3248'
abstract:
- lang: eng
text: We describe RTblob, a high speed vision system that detects objects in cluttered
scenes based on their color and shape at a speed of over 800 frames/s. Because
the system is available as open-source software and relies only on off-the-shelf
PC hardware components, it can provide the basis for multiple application scenarios.
As an illustrative example, we show how RTblob can be used in a robotic table
tennis scenario to estimate ball trajectories through 3D space simultaneously
from four cameras images at a speed of 200 Hz.
article_processing_charge: No
article_type: original
author:
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
- first_name: Jan
full_name: Peters, Jan
last_name: Peters
citation:
ama: Lampert C, Peters J. Real-time detection of colored objects in multiple camera
streams with off-the-shelf hardware components. Journal of Real-Time Image
Processing. 2012;7(1):31-41. doi:10.1007/s11554-010-0168-3
apa: Lampert, C., & Peters, J. (2012). Real-time detection of colored objects
in multiple camera streams with off-the-shelf hardware components. Journal
of Real-Time Image Processing. Springer. https://doi.org/10.1007/s11554-010-0168-3
chicago: Lampert, Christoph, and Jan Peters. “Real-Time Detection of Colored Objects
in Multiple Camera Streams with off-the-Shelf Hardware Components.” Journal
of Real-Time Image Processing. Springer, 2012. https://doi.org/10.1007/s11554-010-0168-3.
ieee: C. Lampert and J. Peters, “Real-time detection of colored objects in multiple
camera streams with off-the-shelf hardware components,” Journal of Real-Time
Image Processing, vol. 7, no. 1. Springer, pp. 31–41, 2012.
ista: Lampert C, Peters J. 2012. Real-time detection of colored objects in multiple
camera streams with off-the-shelf hardware components. Journal of Real-Time Image
Processing. 7(1), 31–41.
mla: Lampert, Christoph, and Jan Peters. “Real-Time Detection of Colored Objects
in Multiple Camera Streams with off-the-Shelf Hardware Components.” Journal
of Real-Time Image Processing, vol. 7, no. 1, Springer, 2012, pp. 31–41, doi:10.1007/s11554-010-0168-3.
short: C. Lampert, J. Peters, Journal of Real-Time Image Processing 7 (2012) 31–41.
corr_author: '1'
date_created: 2018-12-11T12:02:15Z
date_published: 2012-03-01T00:00:00Z
date_updated: 2025-09-30T07:46:36Z
day: '01'
ddc:
- '000'
department:
- _id: ChLa
doi: 10.1007/s11554-010-0168-3
external_id:
isi:
- '000303242600004'
file:
- access_level: open_access
checksum: 241be47ea50e81a283bcf4c45b07e8cc
content_type: application/pdf
creator: kschuh
date_created: 2019-02-12T10:52:25Z
date_updated: 2020-07-14T12:46:04Z
file_id: '5958'
file_name: 2012_Springer_Lampert.pdf
file_size: 2933187
relation: main_file
file_date_updated: 2020-07-14T12:46:04Z
has_accepted_license: '1'
intvolume: ' 7'
isi: 1
issue: '1'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Submitted Version
page: 31 - 41
publication: Journal of Real-Time Image Processing
publication_identifier:
eissn:
- 1861-8219
issn:
- 1861-8200
publication_status: published
publisher: Springer
publist_id: '3417'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Real-time detection of colored objects in multiple camera streams with off-the-shelf
hardware components
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 7
year: '2012'
...
---
_id: '3250'
abstract:
- lang: eng
text: The Learning Parity with Noise (LPN) problem has recently found many applications
in cryptography as the hardness assumption underlying the constructions of "provably
secure" cryptographic schemes like encryption or authentication protocols.
Being provably secure means that the scheme comes with a proof showing that the
existence of an efficient adversary against the scheme implies that the underlying
hardness assumption is wrong. LPN based schemes are appealing for theoretical
and practical reasons. On the theoretical side, LPN based schemes offer a very
strong security guarantee. The LPN problem is equivalent to the problem of decoding
random linear codes, a problem that has been extensively studied in the last half
century. The fastest known algorithms run in exponential time and unlike most
number-theoretic problems used in cryptography, the LPN problem does not succumb
to known quantum algorithms. On the practical side, LPN based schemes are often
extremely simple and efficient in terms of code-size as well as time and space
requirements. This makes them prime candidates for light-weight devices like RFID
tags, which are too weak to implement standard cryptographic primitives like the
AES block-cipher. This talk will be a gentle introduction to provable security
using simple LPN based schemes as examples. Starting from pseudorandom generators
and symmetric key encryption, over secret-key authentication protocols, and, if
time admits, touching on recent constructions of public-key identification, commitments
and zero-knowledge proofs.
alternative_title:
- LNCS
author:
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Pietrzak KZ. Cryptography from learning parity with noise. In: Vol 7147. Springer;
2012:99-114. doi:10.1007/978-3-642-27660-6_9'
apa: 'Pietrzak, K. Z. (2012). Cryptography from learning parity with noise (Vol.
7147, pp. 99–114). Presented at the SOFSEM: Current Trends in Theory and Practice
of Computer Science, Špindlerův Mlýn, Czech Republic: Springer. https://doi.org/10.1007/978-3-642-27660-6_9'
chicago: Pietrzak, Krzysztof Z. “Cryptography from Learning Parity with Noise,”
7147:99–114. Springer, 2012. https://doi.org/10.1007/978-3-642-27660-6_9.
ieee: 'K. Z. Pietrzak, “Cryptography from learning parity with noise,” presented
at the SOFSEM: Current Trends in Theory and Practice of Computer Science, Špindlerův
Mlýn, Czech Republic, 2012, vol. 7147, pp. 99–114.'
ista: 'Pietrzak KZ. 2012. Cryptography from learning parity with noise. SOFSEM:
Current Trends in Theory and Practice of Computer Science, LNCS, vol. 7147, 99–114.'
mla: Pietrzak, Krzysztof Z. Cryptography from Learning Parity with Noise.
Vol. 7147, Springer, 2012, pp. 99–114, doi:10.1007/978-3-642-27660-6_9.
short: K.Z. Pietrzak, in:, Springer, 2012, pp. 99–114.
conference:
end_date: 2012-01-27
location: Špindlerův Mlýn, Czech Republic
name: 'SOFSEM: Current Trends in Theory and Practice of Computer Science'
start_date: 2012-01-21
corr_author: '1'
date_created: 2018-12-11T12:02:15Z
date_published: 2012-02-19T00:00:00Z
date_updated: 2024-10-09T20:54:42Z
day: '19'
department:
- _id: KrPi
doi: 10.1007/978-3-642-27660-6_9
intvolume: ' 7147'
language:
- iso: eng
month: '02'
oa_version: None
page: 99 - 114
publication_status: published
publisher: Springer
publist_id: '3407'
quality_controlled: '1'
scopus_import: 1
status: public
title: Cryptography from learning parity with noise
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 7147
year: '2012'
...
---
_id: '3252'
abstract:
- lang: eng
text: 'We study the automatic synthesis of fair non-repudiation protocols, a class
of fair exchange protocols, used for digital contract signing. First, we show
how to specify the objectives of the participating agents, the trusted third party
(TTP) and the protocols as path formulas in Linear Temporal Logic (LTL) and prove
that the satisfaction of the objectives of the agents and the TTP imply satisfaction
of the protocol objectives. We then show that weak (co-operative) co-synthesis
and classical (strictly competitive) co-synthesis fail in synthesizing these protocols,
whereas assume-guarantee synthesis (AGS) succeeds. We demonstrate the success
of assume-guarantee synthesis as follows: (a) any solution of assume-guarantee
synthesis is attack-free; no subset of participants can violate the objectives
of the other participants without violating their own objectives; (b) the Asokan-Shoup-Waidner
(ASW) certified mail protocol that has known vulnerabilities is not a solution
of AGS; and (c) the Kremer-Markowitch (KM) non-repudiation protocol is a solution
of AGS. To our knowledge this is the first application of synthesis to fair non-repudiation
protocols, and our results show how synthesis can generate correct protocols and
automatically discover vulnerabilities. The solution to assume-guarantee synthesis
can be computed efficiently as the secure equilibrium solution of three-player
graph games. © 2012 Springer-Verlag.'
acknowledgement: "The research was supported by Austrian Science Fund (FWF) Grant
No P 23499-N23 (Modern Graph Algorithmic Techniques in Formal Verification), FWF
NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft
faculty fellows award.\r\nThe authors would like to thank Avik Chaudhuri for his
invaluable help and feedback."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Vishwanath
full_name: Raman, Vishwanath
last_name: Raman
citation:
ama: 'Chatterjee K, Raman V. Synthesizing protocols for digital contract signing.
In: Vol 7148. Springer; 2012:152-168. doi:10.1007/978-3-642-27940-9_11'
apa: 'Chatterjee, K., & Raman, V. (2012). Synthesizing protocols for digital
contract signing (Vol. 7148, pp. 152–168). Presented at the VMCAI: Verification,
Model Checking and Abstract Interpretation, Philadelphia, PA, USA: Springer. https://doi.org/10.1007/978-3-642-27940-9_11'
chicago: Chatterjee, Krishnendu, and Vishwanath Raman. “Synthesizing Protocols for
Digital Contract Signing,” 7148:152–68. Springer, 2012. https://doi.org/10.1007/978-3-642-27940-9_11.
ieee: 'K. Chatterjee and V. Raman, “Synthesizing protocols for digital contract
signing,” presented at the VMCAI: Verification, Model Checking and Abstract Interpretation,
Philadelphia, PA, USA, 2012, vol. 7148, pp. 152–168.'
ista: 'Chatterjee K, Raman V. 2012. Synthesizing protocols for digital contract
signing. VMCAI: Verification, Model Checking and Abstract Interpretation, LNCS,
vol. 7148, 152–168.'
mla: Chatterjee, Krishnendu, and Vishwanath Raman. Synthesizing Protocols for
Digital Contract Signing. Vol. 7148, Springer, 2012, pp. 152–68, doi:10.1007/978-3-642-27940-9_11.
short: K. Chatterjee, V. Raman, in:, Springer, 2012, pp. 152–168.
conference:
end_date: 2012-01-24
location: Philadelphia, PA, USA
name: 'VMCAI: Verification, Model Checking and Abstract Interpretation'
start_date: 2012-01-22
date_created: 2018-12-11T12:02:16Z
date_published: 2012-01-20T00:00:00Z
date_updated: 2025-06-11T08:06:25Z
day: '20'
department:
- _id: KrCh
doi: 10.1007/978-3-642-27940-9_11
ec_funded: 1
external_id:
arxiv:
- '1004.2697'
intvolume: ' 7148'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1004.2697
month: '01'
oa: 1
oa_version: Preprint
page: 152 - 168
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication_status: published
publisher: Springer
publist_id: '3405'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Synthesizing protocols for digital contract signing
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7148
year: '2012'
...
---
_id: '3253'
abstract:
- lang: eng
text: We describe a framework for reasoning about programs with lists carrying integer
numerical data. We use abstract domains to describe and manipulate complex constraints
on configurations of these programs mixing constraints on the shape of the heap,
sizes of the lists, on the multisets of data stored in these lists, and on the
data at their different positions. Moreover, we provide powerful techniques for
automatic validation of Hoare-triples and invariant checking, as well as for automatic
synthesis of invariants and procedure summaries using modular inter-procedural
analysis. The approach has been implemented in a tool called Celia and experimented
successfully on a large benchmark of programs.
acknowledgement: This work was partly supported by the French National Research Agency
(ANR) project Veridyc (ANR-09-SEGI-016).
alternative_title:
- LNCS
author:
- first_name: Ahmed
full_name: Bouajjani, Ahmed
last_name: Bouajjani
- first_name: Cezara
full_name: Dragoi, Cezara
id: 2B2B5ED0-F248-11E8-B48F-1D18A9856A87
last_name: Dragoi
- first_name: Constantin
full_name: Enea, Constantin
last_name: Enea
- first_name: Mihaela
full_name: Sighireanu, Mihaela
last_name: Sighireanu
citation:
ama: 'Bouajjani A, Dragoi C, Enea C, Sighireanu M. Abstract domains for automated
reasoning about list manipulating programs with infinite data. In: Vol 7148. Springer;
2012:1-22. doi:10.1007/978-3-642-27940-9_1'
apa: 'Bouajjani, A., Dragoi, C., Enea, C., & Sighireanu, M. (2012). Abstract
domains for automated reasoning about list manipulating programs with infinite
data (Vol. 7148, pp. 1–22). Presented at the VMCAI: Verification, Model Checking
and Abstract Interpretation, Philadelphia, PA, USA: Springer. https://doi.org/10.1007/978-3-642-27940-9_1'
chicago: Bouajjani, Ahmed, Cezara Dragoi, Constantin Enea, and Mihaela Sighireanu.
“Abstract Domains for Automated Reasoning about List Manipulating Programs with
Infinite Data,” 7148:1–22. Springer, 2012. https://doi.org/10.1007/978-3-642-27940-9_1.
ieee: 'A. Bouajjani, C. Dragoi, C. Enea, and M. Sighireanu, “Abstract domains for
automated reasoning about list manipulating programs with infinite data,” presented
at the VMCAI: Verification, Model Checking and Abstract Interpretation, Philadelphia,
PA, USA, 2012, vol. 7148, pp. 1–22.'
ista: 'Bouajjani A, Dragoi C, Enea C, Sighireanu M. 2012. Abstract domains for automated
reasoning about list manipulating programs with infinite data. VMCAI: Verification,
Model Checking and Abstract Interpretation, LNCS, vol. 7148, 1–22.'
mla: Bouajjani, Ahmed, et al. Abstract Domains for Automated Reasoning about
List Manipulating Programs with Infinite Data. Vol. 7148, Springer, 2012,
pp. 1–22, doi:10.1007/978-3-642-27940-9_1.
short: A. Bouajjani, C. Dragoi, C. Enea, M. Sighireanu, in:, Springer, 2012, pp.
1–22.
conference:
end_date: 2012-01-24
location: Philadelphia, PA, USA
name: 'VMCAI: Verification, Model Checking and Abstract Interpretation'
start_date: 2012-01-22
date_created: 2018-12-11T12:02:17Z
date_published: 2012-02-26T00:00:00Z
date_updated: 2024-10-21T06:02:58Z
day: '26'
department:
- _id: ToHe
doi: 10.1007/978-3-642-27940-9_1
intvolume: ' 7148'
language:
- iso: eng
month: '02'
oa_version: None
page: 1 - 22
publication_status: published
publisher: Springer
publist_id: '3404'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Abstract domains for automated reasoning about list manipulating programs with
infinite data
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 7148
year: '2012'
...
---
_id: '3254'
abstract:
- lang: eng
text: 'The theory of graph games with ω-regular winning conditions is the foundation
for modeling and synthesizing reactive processes. In the case of stochastic reactive
processes, the corresponding stochastic graph games have three players, two of
them (System and Environment) behaving adversarially, and the third (Uncertainty)
behaving probabilistically. We consider two problems for stochastic graph games:
the qualitative problem asks for the set of states from which a player can win
with probability 1 (almost-sure winning); and the quantitative problem asks for
the maximal probability of winning (optimal winning) from each state. We consider
ω-regular winning conditions formalized as Müller winning conditions. We present
optimal memory bounds for pure (deterministic) almost-sure winning and optimal
winning strategies in stochastic graph games with Müller winning conditions. We
also study the complexity of stochastic Müller games and show that both the qualitative
and quantitative analysis problems are PSPACE-complete. Our results are relevant
in synthesis of stochastic reactive processes.'
acknowledgement: 'The research was supported by Austrian Science Fund (FWF) Grant
No. P 23499-N23, FWF NFN Grant No. S11407-N23 (RiSE), ERC Start grant (279307: Graph
Games), and Microsoft faculty fellows award.'
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
citation:
ama: Chatterjee K. The complexity of stochastic Müller games. Information and
Computation. 2012;211:29-48. doi:10.1016/j.ic.2011.11.004
apa: Chatterjee, K. (2012). The complexity of stochastic Müller games. Information
and Computation. Elsevier. https://doi.org/10.1016/j.ic.2011.11.004
chicago: Chatterjee, Krishnendu. “The Complexity of Stochastic Müller Games.” Information
and Computation. Elsevier, 2012. https://doi.org/10.1016/j.ic.2011.11.004.
ieee: K. Chatterjee, “The complexity of stochastic Müller games,” Information
and Computation, vol. 211. Elsevier, pp. 29–48, 2012.
ista: Chatterjee K. 2012. The complexity of stochastic Müller games. Information
and Computation. 211, 29–48.
mla: Chatterjee, Krishnendu. “The Complexity of Stochastic Müller Games.” Information
and Computation, vol. 211, Elsevier, 2012, pp. 29–48, doi:10.1016/j.ic.2011.11.004.
short: K. Chatterjee, Information and Computation 211 (2012) 29–48.
corr_author: '1'
date_created: 2018-12-11T12:02:17Z
date_published: 2012-02-01T00:00:00Z
date_updated: 2025-09-30T07:45:01Z
day: '01'
department:
- _id: KrCh
doi: 10.1016/j.ic.2011.11.004
ec_funded: 1
external_id:
isi:
- '000300468000002'
intvolume: ' 211'
isi: 1
language:
- iso: eng
main_file_link:
- url: http://arise.or.at/pubpdf/The_complexity_of_stochastic_M___u_ller_games.pdf
month: '02'
oa_version: None
page: 29 - 48
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: Information and Computation
publication_status: published
publisher: Elsevier
publist_id: '3403'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The complexity of stochastic Müller games
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 211
year: '2012'
...
---
_id: '3255'
abstract:
- lang: eng
text: In this paper we survey results of two-player games on graphs and Markov decision
processes with parity, mean-payoff and energy objectives, and the combination
of mean-payoff and energy objectives with parity objectives. These problems have
applications in verification and synthesis of reactive systems in resource-constrained
environments.
acknowledgement: This work was partially supported by FWF NFN Grant S11407-N23 (RiSE)
and a Microsoft faculty fellowship.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Laurent
full_name: Doyen, Laurent
last_name: Doyen
citation:
ama: 'Chatterjee K, Doyen L. Games and Markov decision processes with mean payoff
parity and energy parity objectives. In: Vol 7119. Springer; 2012:37-46. doi:10.1007/978-3-642-25929-6_3'
apa: 'Chatterjee, K., & Doyen, L. (2012). Games and Markov decision processes
with mean payoff parity and energy parity objectives (Vol. 7119, pp. 37–46). Presented
at the MEMICS: Mathematical and Engineering Methods in Computer Science, Lednice,
Czech Republic: Springer. https://doi.org/10.1007/978-3-642-25929-6_3'
chicago: Chatterjee, Krishnendu, and Laurent Doyen. “Games and Markov Decision Processes
with Mean Payoff Parity and Energy Parity Objectives,” 7119:37–46. Springer, 2012.
https://doi.org/10.1007/978-3-642-25929-6_3.
ieee: 'K. Chatterjee and L. Doyen, “Games and Markov decision processes with mean
payoff parity and energy parity objectives,” presented at the MEMICS: Mathematical
and Engineering Methods in Computer Science, Lednice, Czech Republic, 2012, vol.
7119, pp. 37–46.'
ista: 'Chatterjee K, Doyen L. 2012. Games and Markov decision processes with mean
payoff parity and energy parity objectives. MEMICS: Mathematical and Engineering
Methods in Computer Science, LNCS, vol. 7119, 37–46.'
mla: Chatterjee, Krishnendu, and Laurent Doyen. Games and Markov Decision Processes
with Mean Payoff Parity and Energy Parity Objectives. Vol. 7119, Springer,
2012, pp. 37–46, doi:10.1007/978-3-642-25929-6_3.
short: K. Chatterjee, L. Doyen, in:, Springer, 2012, pp. 37–46.
conference:
end_date: 2011-10-16
location: Lednice, Czech Republic
name: 'MEMICS: Mathematical and Engineering Methods in Computer Science'
start_date: 2011-10-14
date_created: 2018-12-11T12:02:17Z
date_published: 2012-01-01T00:00:00Z
date_updated: 2021-01-12T07:42:10Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1007/978-3-642-25929-6_3
file:
- access_level: open_access
checksum: eed2cc1e76b160418c977e76e8899a60
content_type: application/pdf
creator: dernst
date_created: 2020-05-15T12:53:12Z
date_updated: 2020-07-14T12:46:05Z
file_id: '7863'
file_name: 2012_MEMICS_Chatterjee.pdf
file_size: 114060
relation: main_file
file_date_updated: 2020-07-14T12:46:05Z
has_accepted_license: '1'
intvolume: ' 7119'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
page: 37 - 46
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
publication_status: published
publisher: Springer
publist_id: '3400'
quality_controlled: '1'
scopus_import: 1
status: public
title: Games and Markov decision processes with mean payoff parity and energy parity
objectives
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7119
year: '2012'
...
---
_id: '3256'
abstract:
- lang: eng
text: We use a distortion to define the dual complex of a cubical subdivision of
ℝ n as an n-dimensional subcomplex of the nerve of the set of n-cubes. Motivated
by the topological analysis of high-dimensional digital image data, we consider
such subdivisions defined by generalizations of quad- and oct-trees to n dimensions.
Assuming the subdivision is balanced, we show that mapping each vertex to the
center of the corresponding n-cube gives a geometric realization of the dual complex
in ℝ n.
acknowledgement: This research is partially supported by the Defense Advanced Research
Projects Agency (DARPA) under grants HR0011-05-1-0057 and HR0011-09-0065 as well
as the National Science Foundation (NSF) under grant DBI-0820624.
article_processing_charge: No
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
citation:
ama: Edelsbrunner H, Kerber M. Dual complexes of cubical subdivisions of ℝn. Discrete
& Computational Geometry. 2012;47(2):393-414. doi:10.1007/s00454-011-9382-4
apa: Edelsbrunner, H., & Kerber, M. (2012). Dual complexes of cubical subdivisions
of ℝn. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-011-9382-4
chicago: Edelsbrunner, Herbert, and Michael Kerber. “Dual Complexes of Cubical Subdivisions
of ℝn.” Discrete & Computational Geometry. Springer, 2012. https://doi.org/10.1007/s00454-011-9382-4.
ieee: H. Edelsbrunner and M. Kerber, “Dual complexes of cubical subdivisions of
ℝn,” Discrete & Computational Geometry, vol. 47, no. 2. Springer, pp.
393–414, 2012.
ista: Edelsbrunner H, Kerber M. 2012. Dual complexes of cubical subdivisions of
ℝn. Discrete & Computational Geometry. 47(2), 393–414.
mla: Edelsbrunner, Herbert, and Michael Kerber. “Dual Complexes of Cubical Subdivisions
of ℝn.” Discrete & Computational Geometry, vol. 47, no. 2, Springer,
2012, pp. 393–414, doi:10.1007/s00454-011-9382-4.
short: H. Edelsbrunner, M. Kerber, Discrete & Computational Geometry 47 (2012)
393–414.
corr_author: '1'
date_created: 2018-12-11T12:02:17Z
date_published: 2012-03-01T00:00:00Z
date_updated: 2025-09-30T07:43:46Z
day: '01'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.1007/s00454-011-9382-4
external_id:
isi:
- '000299057200010'
file:
- access_level: open_access
checksum: 76486f3b2c9e7fd81342f3832ca387e7
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:08:15Z
date_updated: 2020-07-14T12:46:05Z
file_id: '4675'
file_name: IST-2016-543-v1+1_2012-J-08-HierarchyCubeComplex.pdf
file_size: 203636
relation: main_file
file_date_updated: 2020-07-14T12:46:05Z
has_accepted_license: '1'
intvolume: ' 47'
isi: 1
issue: '2'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Submitted Version
page: 393 - 414
publication: Discrete & Computational Geometry
publication_status: published
publisher: Springer
publist_id: '3398'
pubrep_id: '543'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Dual complexes of cubical subdivisions of ℝn
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 47
year: '2012'
...
---
_id: '3257'
abstract:
- lang: eng
text: Consider a convex relaxation f̂ of a pseudo-Boolean function f. We say that
the relaxation is totally half-integral if f̂(x) is a polyhedral function with
half-integral extreme points x, and this property is preserved after adding an
arbitrary combination of constraints of the form x i=x j, x i=1-x j, and x i=γ
where γ∈{0,1,1/2} is a constant. A well-known example is the roof duality relaxation
for quadratic pseudo-Boolean functions f. We argue that total half-integrality
is a natural requirement for generalizations of roof duality to arbitrary pseudo-Boolean
functions. Our contributions are as follows. First, we provide a complete characterization
of totally half-integral relaxations f̂ by establishing a one-to-one correspondence
with bisubmodular functions. Second, we give a new characterization of bisubmodular
functions. Finally, we show some relationships between general totally half-integral
relaxations and relaxations based on the roof duality. On the conceptual level,
our results show that bisubmodular functions provide a natural generalization
of the roof duality approach to higher-order terms. This can be viewed as a non-submodular
analogue of the fact that submodular functions generalize the s-t minimum cut
problem with non-negative weights to higher-order terms.
article_processing_charge: No
arxiv: 1
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: Kolmogorov V. Generalized roof duality and bisubmodular functions. Discrete
Applied Mathematics. 2012;160(4-5):416-426. doi:10.1016/j.dam.2011.10.026
apa: Kolmogorov, V. (2012). Generalized roof duality and bisubmodular functions.
Discrete Applied Mathematics. Elsevier. https://doi.org/10.1016/j.dam.2011.10.026
chicago: Kolmogorov, Vladimir. “Generalized Roof Duality and Bisubmodular Functions.”
Discrete Applied Mathematics. Elsevier, 2012. https://doi.org/10.1016/j.dam.2011.10.026.
ieee: V. Kolmogorov, “Generalized roof duality and bisubmodular functions,” Discrete
Applied Mathematics, vol. 160, no. 4–5. Elsevier, pp. 416–426, 2012.
ista: Kolmogorov V. 2012. Generalized roof duality and bisubmodular functions. Discrete
Applied Mathematics. 160(4–5), 416–426.
mla: Kolmogorov, Vladimir. “Generalized Roof Duality and Bisubmodular Functions.”
Discrete Applied Mathematics, vol. 160, no. 4–5, Elsevier, 2012, pp. 416–26,
doi:10.1016/j.dam.2011.10.026.
short: V. Kolmogorov, Discrete Applied Mathematics 160 (2012) 416–426.
corr_author: '1'
date_created: 2018-12-11T12:02:18Z
date_published: 2012-03-01T00:00:00Z
date_updated: 2025-09-30T07:43:17Z
day: '01'
department:
- _id: VlKo
doi: 10.1016/j.dam.2011.10.026
external_id:
arxiv:
- '1005.2305'
isi:
- '000301211100006'
intvolume: ' 160'
isi: 1
issue: 4-5
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1005.2305
month: '03'
oa: 1
oa_version: Preprint
page: 416 - 426
publication: Discrete Applied Mathematics
publication_status: published
publisher: Elsevier
publist_id: '3397'
quality_controlled: '1'
related_material:
record:
- id: '2934'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Generalized roof duality and bisubmodular functions
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 160
year: '2012'
...
---
_id: '3262'
abstract:
- lang: eng
text: Living cells must control the reading out or "expression" of information
encoded in their genomes, and this regulation often is mediated by transcription
factors--proteins that bind to DNA and either enhance or repress the expression
of nearby genes. But the expression of transcription factor proteins is itself
regulated, and many transcription factors regulate their own expression in addition
to responding to other input signals. Here we analyze the simplest of such self-regulatory
circuits, asking how parameters can be chosen to optimize information transmission
from inputs to outputs in the steady state. Some nonzero level of self-regulation
is almost always optimal, with self-activation dominant when transcription factor
concentrations are low and self-repression dominant when concentrations are high.
In steady state the optimal self-activation is never strong enough to induce bistability,
although there is a limit in which the optimal parameters are very close to the
critical point.
acknowledgement: "We thank T. Gregor, E. F. Wieschaus, and, especially, C. G. Callan
for helpful discussions.\r\nWork at Princeton was supported in part by NSF Grants
No. PHY–0957573 and No. CCF–0939370, by NIH Grant No. R01 GM077599, and by the W.
M. Keck Foundation. For part of this work, G.T. was supported in part by NSF Grant
No. EF–0928048 and by the Vice Provost for Research at the University of Pennsylvania."
article_number: '041903'
article_processing_charge: No
arxiv: 1
author:
- first_name: Gasper
full_name: Tkacik, Gasper
id: 3D494DCA-F248-11E8-B48F-1D18A9856A87
last_name: Tkacik
orcid: 0000-0002-6699-1455
- first_name: Aleksandra
full_name: Walczak, Aleksandra
last_name: Walczak
- first_name: William
full_name: Bialek, William
last_name: Bialek
citation:
ama: Tkačik G, Walczak A, Bialek W. Optimizing information flow in small genetic
networks. III. A self-interacting gene. Physical Review E statistical nonlinear
and soft matter physics . 2012;85(4). doi:10.1103/PhysRevE.85.041903
apa: Tkačik, G., Walczak, A., & Bialek, W. (2012). Optimizing information flow
in small genetic networks. III. A self-interacting gene. Physical Review E
Statistical Nonlinear and Soft Matter Physics . American Institute of Physics.
https://doi.org/10.1103/PhysRevE.85.041903
chicago: Tkačik, Gašper, Aleksandra Walczak, and William Bialek. “Optimizing Information
Flow in Small Genetic Networks. III. A Self-Interacting Gene.” Physical Review
E Statistical Nonlinear and Soft Matter Physics . American Institute of Physics,
2012. https://doi.org/10.1103/PhysRevE.85.041903.
ieee: G. Tkačik, A. Walczak, and W. Bialek, “Optimizing information flow in small
genetic networks. III. A self-interacting gene,” Physical Review E statistical
nonlinear and soft matter physics , vol. 85, no. 4. American Institute of
Physics, 2012.
ista: Tkačik G, Walczak A, Bialek W. 2012. Optimizing information flow in small
genetic networks. III. A self-interacting gene. Physical Review E statistical
nonlinear and soft matter physics . 85(4), 041903.
mla: Tkačik, Gašper, et al. “Optimizing Information Flow in Small Genetic Networks.
III. A Self-Interacting Gene.” Physical Review E Statistical Nonlinear and
Soft Matter Physics , vol. 85, no. 4, 041903, American Institute of Physics,
2012, doi:10.1103/PhysRevE.85.041903.
short: G. Tkačik, A. Walczak, W. Bialek, Physical Review E Statistical Nonlinear
and Soft Matter Physics 85 (2012).
corr_author: '1'
date_created: 2018-12-11T12:02:20Z
date_published: 2012-04-01T00:00:00Z
date_updated: 2025-09-30T07:41:44Z
day: '01'
department:
- _id: GaTk
doi: 10.1103/PhysRevE.85.041903
external_id:
arxiv:
- '1112.5026'
isi:
- '000302410200006'
intvolume: ' 85'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1112.5026
month: '04'
oa: 1
oa_version: Preprint
publication: ' Physical Review E statistical nonlinear and soft matter physics '
publication_status: published
publisher: American Institute of Physics
publist_id: '3386'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Optimizing information flow in small genetic networks. III. A self-interacting
gene
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 85
year: '2012'
...
---
_id: '3265'
abstract:
- lang: eng
text: We propose a mid-level statistical model for image segmentation that composes
multiple figure-ground hypotheses (FG) obtained by applying constraints at different
locations and scales, into larger interpretations (tilings) of the entire image.
Inference is cast as optimization over sets of maximal cliques sampled from a
graph connecting all non-overlapping figure-ground segment hypotheses. Potential
functions over cliques combine unary, Gestalt-based figure qualities, and pairwise
compatibilities among spatially neighboring segments, constrained by T-junctions
and the boundary interface statistics of real scenes. Learning the model parameters
is based on maximum likelihood, alternating between sampling image tilings and
optimizing their potential function parameters. State of the art results are reported
on the Berkeley and Stanford segmentation datasets, as well as VOC2009, where
a 28% improvement was achieved.
article_number: '6126486'
author:
- first_name: Adrian
full_name: Ion, Adrian
id: 29F89302-F248-11E8-B48F-1D18A9856A87
last_name: Ion
- first_name: Joao
full_name: Carreira, Joao
last_name: Carreira
- first_name: Cristian
full_name: Sminchisescu, Cristian
last_name: Sminchisescu
citation:
ama: 'Ion A, Carreira J, Sminchisescu C. Image segmentation by figure-ground composition
into maximal cliques. In: IEEE; 2012. doi:10.1109/ICCV.2011.6126486'
apa: 'Ion, A., Carreira, J., & Sminchisescu, C. (2012). Image segmentation by
figure-ground composition into maximal cliques. Presented at the ICCV: International
Conference on Computer Vision, Barcelona, Spain: IEEE. https://doi.org/10.1109/ICCV.2011.6126486'
chicago: Ion, Adrian, Joao Carreira, and Cristian Sminchisescu. “Image Segmentation
by Figure-Ground Composition into Maximal Cliques.” IEEE, 2012. https://doi.org/10.1109/ICCV.2011.6126486.
ieee: 'A. Ion, J. Carreira, and C. Sminchisescu, “Image segmentation by figure-ground
composition into maximal cliques,” presented at the ICCV: International Conference
on Computer Vision, Barcelona, Spain, 2012.'
ista: 'Ion A, Carreira J, Sminchisescu C. 2012. Image segmentation by figure-ground
composition into maximal cliques. ICCV: International Conference on Computer Vision,
6126486.'
mla: Ion, Adrian, et al. Image Segmentation by Figure-Ground Composition into
Maximal Cliques. 6126486, IEEE, 2012, doi:10.1109/ICCV.2011.6126486.
short: A. Ion, J. Carreira, C. Sminchisescu, in:, IEEE, 2012.
conference:
end_date: 2011-11-13
location: Barcelona, Spain
name: 'ICCV: International Conference on Computer Vision'
start_date: 2011-11-06
date_created: 2018-12-11T12:02:21Z
date_published: 2012-01-12T00:00:00Z
date_updated: 2021-01-12T07:42:15Z
day: '12'
department:
- _id: HeEd
doi: 10.1109/ICCV.2011.6126486
language:
- iso: eng
month: '01'
oa_version: None
publication_status: published
publisher: IEEE
publist_id: '3382'
quality_controlled: '1'
status: public
title: Image segmentation by figure-ground composition into maximal cliques
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2012'
...
---
_id: '3274'
abstract:
- lang: eng
text: A boundary element model of a tunnel running through horizontally layered
soil with anisotropic material properties is presented. Since there is no analytical
fundamental solution for wave propagation inside a layered orthotropic medium
in 3D, the fundamental displacements and stresses have to be calculated numerically.
In our model this is done in the Fourier domain with respect to space and time.
The assumption of a straight tunnel with infinite extension in the x direction
makes it possible to decouple the system for every wave number kx, leading to
a 2.5D-problem, which is suited for parallel computation. The special form of
the fundamental solution, resulting from our Fourier ansatz, and the fact, that
the calculation of the boundary integral equation is performed in the Fourier
domain, enhances the stability and efficiency of the numerical calculations.
acknowledgement: This work was supported by the Austrian Federal Ministry of Transport,
Innovation and Technology under the Grant Bmvit-isb2 and the FFG under the project
Pr. Nr. 809089.
article_processing_charge: No
author:
- first_name: Georg
full_name: Rieckh, Georg
id: 34DA8BD6-F248-11E8-B48F-1D18A9856A87
last_name: Rieckh
- first_name: Wolfgang
full_name: Kreuzer, Wolfgang
last_name: Kreuzer
- first_name: Holger
full_name: Waubke, Holger
last_name: Waubke
- first_name: Peter
full_name: Balazs, Peter
last_name: Balazs
citation:
ama: Rieckh G, Kreuzer W, Waubke H, Balazs P. A 2.5D-Fourier-BEM model for vibrations
in a tunnel running through layered anisotropic soil. Engineering Analysis
with Boundary Elements. 2012;36(6):960-967. doi:10.1016/j.enganabound.2011.12.014
apa: Rieckh, G., Kreuzer, W., Waubke, H., & Balazs, P. (2012). A 2.5D-Fourier-BEM
model for vibrations in a tunnel running through layered anisotropic soil.
Engineering Analysis with Boundary Elements. Elsevier. https://doi.org/10.1016/j.enganabound.2011.12.014
chicago: Rieckh, Georg, Wolfgang Kreuzer, Holger Waubke, and Peter Balazs. “A 2.5D-Fourier-BEM
Model for Vibrations in a Tunnel Running through Layered Anisotropic Soil.”
Engineering Analysis with Boundary Elements. Elsevier, 2012. https://doi.org/10.1016/j.enganabound.2011.12.014.
ieee: G. Rieckh, W. Kreuzer, H. Waubke, and P. Balazs, “A 2.5D-Fourier-BEM model
for vibrations in a tunnel running through layered anisotropic soil,” Engineering
Analysis with Boundary Elements, vol. 36, no. 6. Elsevier, pp. 960–967, 2012.
ista: Rieckh G, Kreuzer W, Waubke H, Balazs P. 2012. A 2.5D-Fourier-BEM model for
vibrations in a tunnel running through layered anisotropic soil. Engineering
Analysis with Boundary Elements. 36(6), 960–967.
mla: Rieckh, Georg, et al. “A 2.5D-Fourier-BEM Model for Vibrations in a Tunnel
Running through Layered Anisotropic Soil.” Engineering Analysis with Boundary
Elements, vol. 36, no. 6, Elsevier, 2012, pp. 960–67, doi:10.1016/j.enganabound.2011.12.014.
short: G. Rieckh, W. Kreuzer, H. Waubke, P. Balazs, Engineering Analysis with Boundary
Elements 36 (2012) 960–967.
corr_author: '1'
date_created: 2018-12-11T12:02:24Z
date_published: 2012-06-01T00:00:00Z
date_updated: 2025-09-30T07:41:13Z
day: '01'
department:
- _id: GaTk
doi: 10.1016/j.enganabound.2011.12.014
external_id:
isi:
- '000301691600005'
intvolume: ' 36'
isi: 1
issue: '6'
language:
- iso: eng
month: '06'
oa_version: None
page: 960 - 967
publication: ' Engineering Analysis with Boundary Elements'
publication_status: published
publisher: Elsevier
publist_id: '3372'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A 2.5D-Fourier-BEM model for vibrations in a tunnel running through layered
anisotropic soil
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 36
year: '2012'
...
---
_id: '3277'
abstract:
- lang: eng
text: The problem of the origin of metazoa is becoming more urgent in the context
of astrobiology. By now it is clear that clues to the understanding of this crucial
transition in the evolution of life can arise in a fourth pathway besides the
three possibilities in the quest for simplicity outlined by Bonner in his classical
book. In other words, solar system exploration seems to be one way in the long-term
to elucidate the simplicity of evolutionary development. We place these ideas
in the context of different inheritance systems, namely the genotypic and phenotypic
replicators with limited or unlimited heredity, and ask which of these can support
multicellular development, and to which degree of complexity. However, the quest
for evidence on the evolution of biotas from planets around other stars does not
seem to be feasible with present technology with direct visualization of living
organisms on exoplanets. But this may be attempted on the Galilean moons of Jupiter
where there is a possibility of detecting reliable biomarkers in the next decade
with the Europa Jupiter System Mission, in view of recent progress by landing
micropenetrators on planetary, or satellite surfaces. Mars is a second possibility
in the inner Solar System, in spite of the multiple difficulties faced by the
fleet of past, present and future missions. We discuss a series of preliminary
ideas for elucidating the origin of metazoan analogues with available instrumentation
in potential payloads of feasible space missions to the Galilean moons.
alternative_title:
- Cellular Origin, Life in Extreme Habitats and Astrobiology
author:
- first_name: Harold
full_name: de Vladar, Harold
id: 2A181218-F248-11E8-B48F-1D18A9856A87
last_name: de Vladar
orcid: 0000-0002-5985-7653
- first_name: Julian
full_name: Chela Flores, Julian
last_name: Chela Flores
citation:
ama: 'de Vladar H, Chela Flores J. Can the evolution of multicellularity be anticipated
in the exploration of the solar system? In: Life on Earth and Other Planetary
Bodies. Vol 24. Springer; 2012:387-405. doi:10.1007/978-94-007-4966-5_22'
apa: de Vladar, H., & Chela Flores, J. (2012). Can the evolution of multicellularity
be anticipated in the exploration of the solar system? In Life on Earth and
other planetary bodies (Vol. 24, pp. 387–405). Springer. https://doi.org/10.1007/978-94-007-4966-5_22
chicago: Vladar, Harold de, and Julian Chela Flores. “Can the Evolution of Multicellularity
Be Anticipated in the Exploration of the Solar System?” In Life on Earth and
Other Planetary Bodies, 24:387–405. Springer, 2012. https://doi.org/10.1007/978-94-007-4966-5_22.
ieee: H. de Vladar and J. Chela Flores, “Can the evolution of multicellularity be
anticipated in the exploration of the solar system?,” in Life on Earth and
other planetary bodies, vol. 24, Springer, 2012, pp. 387–405.
ista: 'de Vladar H, Chela Flores J. 2012.Can the evolution of multicellularity be
anticipated in the exploration of the solar system? In: Life on Earth and other
planetary bodies. Cellular Origin, Life in Extreme Habitats and Astrobiology,
vol. 24, 387–405.'
mla: de Vladar, Harold, and Julian Chela Flores. “Can the Evolution of Multicellularity
Be Anticipated in the Exploration of the Solar System?” Life on Earth and Other
Planetary Bodies, vol. 24, Springer, 2012, pp. 387–405, doi:10.1007/978-94-007-4966-5_22.
short: H. de Vladar, J. Chela Flores, in:, Life on Earth and Other Planetary Bodies,
Springer, 2012, pp. 387–405.
corr_author: '1'
date_created: 2018-12-11T12:02:25Z
date_published: 2012-01-01T00:00:00Z
date_updated: 2024-10-09T20:54:39Z
day: '01'
department:
- _id: NiBa
doi: 10.1007/978-94-007-4966-5_22
intvolume: ' 24'
language:
- iso: eng
month: '01'
oa_version: None
page: 387 - 405
publication: Life on Earth and other planetary bodies
publication_status: published
publisher: Springer
publist_id: '3369'
quality_controlled: '1'
status: public
title: Can the evolution of multicellularity be anticipated in the exploration of
the solar system?
type: book_chapter
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 24
year: '2012'
...
---
_id: '3279'
abstract:
- lang: eng
text: "We show a hardness-preserving construction of a PRF from any length doubling
PRG which improves upon known constructions whenever we can put a non-trivial
upper bound q on the number of queries to the PRF. Our construction requires only
O(logq) invocations to the underlying PRG with each query. In comparison, the
number of invocations by the best previous hardness-preserving construction (GGM
using Levin's trick) is logarithmic in the hardness of the PRG. For example, starting
from an exponentially secure PRG {0,1} n → {0,1} 2n, we get a PRF which is exponentially
secure if queried at most q = exp(√n)times and where each invocation of the PRF
requires Θ(√n) queries to the underlying PRG. This is much less than the Θ(n)
required by known constructions. \r\n"
acknowledgement: Supported by the European Research Council under the European Union’s
Seventh Framework Programme (FP7/2007-2013) / ERC Starting Grant (259668-PSPC)
alternative_title:
- LNCS
author:
- first_name: Abhishek
full_name: Jain, Abhishek
last_name: Jain
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Aris
full_name: Tentes, Aris
last_name: Tentes
citation:
ama: 'Jain A, Pietrzak KZ, Tentes A. Hardness preserving constructions of pseudorandom
functions. In: Vol 7194. Springer; 2012:369-382. doi:10.1007/978-3-642-28914-9_21'
apa: 'Jain, A., Pietrzak, K. Z., & Tentes, A. (2012). Hardness preserving constructions
of pseudorandom functions (Vol. 7194, pp. 369–382). Presented at the TCC: Theory
of Cryptography Conference, Taormina, Sicily, Italy: Springer. https://doi.org/10.1007/978-3-642-28914-9_21'
chicago: Jain, Abhishek, Krzysztof Z Pietrzak, and Aris Tentes. “Hardness Preserving
Constructions of Pseudorandom Functions,” 7194:369–82. Springer, 2012. https://doi.org/10.1007/978-3-642-28914-9_21.
ieee: 'A. Jain, K. Z. Pietrzak, and A. Tentes, “Hardness preserving constructions
of pseudorandom functions,” presented at the TCC: Theory of Cryptography Conference,
Taormina, Sicily, Italy, 2012, vol. 7194, pp. 369–382.'
ista: 'Jain A, Pietrzak KZ, Tentes A. 2012. Hardness preserving constructions of
pseudorandom functions. TCC: Theory of Cryptography Conference, LNCS, vol. 7194,
369–382.'
mla: Jain, Abhishek, et al. Hardness Preserving Constructions of Pseudorandom
Functions. Vol. 7194, Springer, 2012, pp. 369–82, doi:10.1007/978-3-642-28914-9_21.
short: A. Jain, K.Z. Pietrzak, A. Tentes, in:, Springer, 2012, pp. 369–382.
conference:
end_date: 2012-03-21
location: Taormina, Sicily, Italy
name: 'TCC: Theory of Cryptography Conference'
start_date: 2012-03-19
date_created: 2018-12-11T12:02:25Z
date_published: 2012-05-04T00:00:00Z
date_updated: 2021-01-12T07:42:21Z
day: '04'
department:
- _id: KrPi
doi: 10.1007/978-3-642-28914-9_21
ec_funded: 1
intvolume: ' 7194'
language:
- iso: eng
main_file_link:
- url: http://www.iacr.org/archive/tcc2012/tcc2012-index.html
month: '05'
oa_version: None
page: 369 - 382
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication_status: published
publisher: Springer
publist_id: '3367'
quality_controlled: '1'
scopus_import: 1
status: public
title: Hardness preserving constructions of pseudorandom functions
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 7194
year: '2012'
...
---
_id: '3280'
abstract:
- lang: eng
text: 'The (decisional) learning with errors problem (LWE) asks to distinguish "noisy"
inner products of a secret vector with random vectors from uniform. The learning
parities with noise problem (LPN) is the special case where the elements of the
vectors are bits. In recent years, the LWE and LPN problems have found many applications
in cryptography. In this paper we introduce a (seemingly) much stronger adaptive
assumption, called "subspace LWE" (SLWE), where the adversary can learn
the inner product of the secret and random vectors after they were projected into
an adaptively and adversarially chosen subspace. We prove that, surprisingly,
the SLWE problem mapping into subspaces of dimension d is almost as hard as LWE
using secrets of length d (the other direction is trivial.) This result immediately
implies that several existing cryptosystems whose security is based on the hardness
of the LWE/LPN problems are provably secure in a much stronger sense than anticipated.
As an illustrative example we show that the standard way of using LPN for symmetric
CPA secure encryption is even secure against a very powerful class of related
key attacks. '
acknowledgement: Supported by the European Research Council under the European Union’s
Seventh Framework Programme (FP7/2007-2013) / ERC Starting Grant (259668-PSPC).
alternative_title:
- LNCS
author:
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Pietrzak KZ. Subspace LWE. In: Vol 7194. Springer; 2012:548-563. doi:10.1007/978-3-642-28914-9_31'
apa: 'Pietrzak, K. Z. (2012). Subspace LWE (Vol. 7194, pp. 548–563). Presented at
the TCC: Theory of Cryptography Conference, Taormina, Sicily, Italy: Springer.
https://doi.org/10.1007/978-3-642-28914-9_31'
chicago: Pietrzak, Krzysztof Z. “Subspace LWE,” 7194:548–63. Springer, 2012. https://doi.org/10.1007/978-3-642-28914-9_31.
ieee: 'K. Z. Pietrzak, “Subspace LWE,” presented at the TCC: Theory of Cryptography
Conference, Taormina, Sicily, Italy, 2012, vol. 7194, pp. 548–563.'
ista: 'Pietrzak KZ. 2012. Subspace LWE. TCC: Theory of Cryptography Conference,
LNCS, vol. 7194, 548–563.'
mla: Pietrzak, Krzysztof Z. Subspace LWE. Vol. 7194, Springer, 2012, pp.
548–63, doi:10.1007/978-3-642-28914-9_31.
short: K.Z. Pietrzak, in:, Springer, 2012, pp. 548–563.
conference:
end_date: 2012-03-21
location: Taormina, Sicily, Italy
name: 'TCC: Theory of Cryptography Conference'
start_date: 2012-03-19
corr_author: '1'
date_created: 2018-12-11T12:02:26Z
date_published: 2012-05-04T00:00:00Z
date_updated: 2024-10-21T06:02:59Z
day: '04'
department:
- _id: KrPi
doi: 10.1007/978-3-642-28914-9_31
ec_funded: 1
intvolume: ' 7194'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://www.iacr.org/archive/tcc2012/71940166/71940166.pdf
month: '05'
oa: 1
oa_version: Submitted Version
page: 548 - 563
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication_status: published
publisher: Springer
publist_id: '3366'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Subspace LWE
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 7194
year: '2012'
...
---
_id: '3281'
abstract:
- lang: eng
text: 'We consider the problem of amplifying the "lossiness" of functions.
We say that an oracle circuit C*: {0,1} m → {0,1}* amplifies relative lossiness
from ℓ/n to L/m if for every function f:{0,1} n → {0,1} n it holds that 1 If f
is injective then so is C f. 2 If f has image size of at most 2 n-ℓ, then C f
has image size at most 2 m-L. The question is whether such C* exists for L/m ≫
ℓ/n. This problem arises naturally in the context of cryptographic "lossy
functions," where the relative lossiness is the key parameter. We show that
for every circuit C* that makes at most t queries to f, the relative lossiness
of C f is at most L/m ≤ ℓ/n + O(log t)/n. In particular, no black-box method making
a polynomial t = poly(n) number of queries can amplify relative lossiness by more
than an O(logn)/n additive term. We show that this is tight by giving a simple
construction (cascading with some randomization) that achieves such amplification.'
acknowledgement: "We would like to thank Oded Goldreich and Omer Rein- gold for discussions
at an early stage of this project, and Scott Aaronson for clarifications regarding
the collision problem.\r\n"
alternative_title:
- LNCS
author:
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Alon
full_name: Rosen, Alon
last_name: Rosen
- first_name: Gil
full_name: Segev, Gil
last_name: Segev
citation:
ama: 'Pietrzak KZ, Rosen A, Segev G. Lossy functions do not amplify well. In: Vol
7194. Springer; 2012:458-475. doi:10.1007/978-3-642-28914-9_26'
apa: 'Pietrzak, K. Z., Rosen, A., & Segev, G. (2012). Lossy functions do not
amplify well (Vol. 7194, pp. 458–475). Presented at the TCC: Theory of Cryptography
Conference, Taormina, Sicily, Italy: Springer. https://doi.org/10.1007/978-3-642-28914-9_26'
chicago: Pietrzak, Krzysztof Z, Alon Rosen, and Gil Segev. “Lossy Functions Do Not
Amplify Well,” 7194:458–75. Springer, 2012. https://doi.org/10.1007/978-3-642-28914-9_26.
ieee: 'K. Z. Pietrzak, A. Rosen, and G. Segev, “Lossy functions do not amplify well,”
presented at the TCC: Theory of Cryptography Conference, Taormina, Sicily, Italy,
2012, vol. 7194, pp. 458–475.'
ista: 'Pietrzak KZ, Rosen A, Segev G. 2012. Lossy functions do not amplify well.
TCC: Theory of Cryptography Conference, LNCS, vol. 7194, 458–475.'
mla: Pietrzak, Krzysztof Z., et al. Lossy Functions Do Not Amplify Well.
Vol. 7194, Springer, 2012, pp. 458–75, doi:10.1007/978-3-642-28914-9_26.
short: K.Z. Pietrzak, A. Rosen, G. Segev, in:, Springer, 2012, pp. 458–475.
conference:
end_date: 2012-03-21
location: Taormina, Sicily, Italy
name: 'TCC: Theory of Cryptography Conference'
start_date: 2012-03-19
date_created: 2018-12-11T12:02:26Z
date_published: 2012-05-04T00:00:00Z
date_updated: 2024-10-21T06:03:00Z
day: '04'
department:
- _id: KrPi
doi: 10.1007/978-3-642-28914-9_26
intvolume: ' 7194'
language:
- iso: eng
main_file_link:
- url: http://www.iacr.org/archive/tcc2012/tcc2012-index.html
month: '05'
oa_version: None
page: 458 - 475
publication_status: published
publisher: Springer
publist_id: '3365'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Lossy functions do not amplify well
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 7194
year: '2012'
...