1.6k citations
- IBM Research - Thomas J. Watson Research CenterUS7 papers
- University of BristolGB3 papers
- Columbia UniversityUS2 papers
- IBM Research - AlmadenUS2 papers
- Kyoto UniversityJP2 papers
- Stanford UniversityUS2 papers
- University of AmsterdamNL2 papers
- University of MichiganUS2 papers
- Vassar CollegeUS2 papers
- Amsterdam University of the ArtsNL1 paper
- California Institute of TechnologyUS1 paper
- Centrum Wiskunde & InformaticaNL1 paper
6 papers · 1 filter
The capacity of a quantum channel for simultaneous transmission of classical and quantum information
I. Devetak, P. W. Shor
An expression is derived characterizing the set of admissible rate pairs for simultaneous transmission of classical and quantum information over a given quantum channel, generalizi…
The Satisfiability Threshold of Random 3-SAT Is at Least 3.52
MohammadTaghi Hajiaghayi, Gregory B. Sorkin
We prove that a random 3-SAT instance with clause-to-variable density less than 3.52 is satisfiable with high probability. The proof comes through an algorithm which selects (and s…
Scale-free brain functional networks
Victor M. Eguiluz, Dante R. Chialvo, Guillermo A. Cecchi +2
Functional magnetic resonance imaging (fMRI) is used to extract {\em functional networks} connecting correlated human brain sites. Analysis of the resulting networks in different t…
Leibniz, Information, Math and Physics
G. J. Chaitin
The information-theoretic point of view proposed by Leibniz in 1686 and developed by algorithmic information theory (AIT) suggests that mathematics and physics are not that differe…
Distillation of secret key and entanglement from quantum states
Igor Devetak, Andreas Winter
We study and solve the problem of distilling secret key from quantum states representing correlation between two parties (Alice and Bob) and an eavesdropper (Eve) via one-way publi…
From Philosophy to Program Size
G. J. Chaitin
Most work on computational complexity is concerned with time. However this course will try to show that program-size complexity, which measures algorithmic information, is of much…