Research Abstracts - 2007

Theory

| A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |

A

• Adaptive Scheduling with Parallelism Feedback
     Kunal Agrawal, Yu Xiong He (NUS), Wen Jing Hsu (NTU) & Charles E. Leiserson
• Memory Models for Open-Nested Transactions
     Kunal Agrawal, Charles E. Leiserson & Jim Sukha
• Testing K-Wise and Almost K-Wise Independence
     N. Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld & Ning Xie

B

• Geometric Folding Algorithms
     Nadia M. Benbernou, Erik D. Demaine, Martin L. Demaine & others
• Streaming Cache-Oblivious B-Trees
     Michael A. Bender, Martin Farach-Colton, Jeremy T. Fineman, Yonatan Fogel, Bradley C. Kuszmaul, Jelani Nelson & Chris Wright
• Cache-Oblivious String B-Trees
     Michael A. Bender, Martin Farach-Colton & Bradley C. Kuszmaul
• Virtual Infrastructure: Abstractions for Mobile Ad Hoc Networks
     Matt Brown, Shlomi Dolev, Seth Gilbert, Limor Lahiani, Nancy Lynch, Sayan Mitra, Calvin Newport, Tina Nolte, Elad Schiller, Alex Shvartsman, Mike Spindel & Jennifer Welch

C

• Task-PIOAs and Security Verification
    Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch, Sayan Mitra, Olivier Pereira & Roberto Segala
• Betting on Permutations
     Yiling Chen, Lance Fortnow, Evdokia Nikolova & David Pennock
• Group Key Management Using Attribute-Based Encryption
     Ling Cheung, Joseph Cooley, Roger Khazan & Calvin Newport

D

• Decoding the Inka Khipu
     Erik D. Demaine, Martin L. Demaine & others
• Bidimensionality Theory
     Erik D. Demaine & MohammadTaghi Hajiaghayi
• PTASs for Planar Graphs and Generalizations
     Erik D. Demaine & MohammadTaghi Hajiaghayi
• Algorithmic Combinatorial Game Theory
     Erik D. Demaine & Bob Hearn
• Network Pricing via Stackelberg Games
     Erik D. Demaine & Oren Weimann
• Computational Geometry through the Information Lens
     Erik D. Demaine & Mihai Patrascu
• Lower Bounds for Dynamic Data Structures
     Erik D. Demaine & Mihai Patrascu
• Oblivious Byzantine Gossip in a Multi-Channel Radio Network
     Shlomi Dolev, Seth Gilbert, Rachid Guerraoui & Calvin Newport

G

• Of Malicious Motes and Suspicious Sensors: On the Efficiency of Malicious Interference in Wireless Networks
     Seth Gilbert, Rachid Guerraoui & Calvin Newport
• Designing Efficient Program Checkers by Delegating Their Work
     Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman & Guy N. Rothblum
• Random Selection and Byzantine Agreement in the Full-Information Model
     Shafi Goldwasser, Elan Pavlov & Vinod Vaikuntanathan
• On Best-Possible Obfuscation
     Shafi Goldwasser & Guy N. Rothblum
• Local Decoding and Testing for Homomorphisms
     Elena Grigorescu, Swastic Kopparty & Madhu Sudan
• Verifying and Decoding in Constant Depth
     Dan Gutfreund, Alexander Healy, Tali Kaufman & Guy N. Rothblum

H

• Securely Obfuscating Re-Encryption
     Susan Hohenberger, Guy N. Rothblum, Abhi Shelat & Vinod Vaikuntanathan
• Making Reusable Structured Data on The Web Cheaper
     David F. Huynh, Robert C. Miller & David R. Karger

J

• Universal Goal-oriented Communication
     Brendan Juba & Madhu Sudan

K

• On the Expected VCG Overpayment in Large Networks
     David Karger & Evdokia Nikolova
• Breaking The Epsilon-Soundness Bound of the Linearity Test Over GF(2)
     Tali Kaufman, S. Litsyn & Ning Xie
• Algebraic Property Testing
     Tali Kaufman & Madhu Sudan
• On the Hardness and Smoothed Complexity of Quasi-concave Minimization
     Jon Kelner & Evdokia Nikolova

M

• Duplicate Detection in Semi-Structured Data
     Nicholas E. Matsakis & David Karger

N

• A Strategic Model for Information Markets
      Evdokia Nikolova & Rahul Sami
• Self-Stabilizing Hierarchical Tracking
      Tina Nolte, Murat Demirbas, Nancy Lynch & Anish Arora

S

• Limits to List Decoding Reed-Solomon Codes
      Eli Ben-Sasson, Swastik Kopparty & Jaikumar Radhakrishnan
• Pairwise Global Alignment of Protein Interaction Networks by Matching Neighborhood Topology
     Rohit Singh, Jinbo Xu & Bonnie Berger
• Struct2Net: Integrating Structure Into Protein-Protein Interaction Prediction
     Rohit Singh, Jinbo Xu & Bonnie Berger

W

• Density-Equalizing Euclidean Minimum Spanning trees for the Detection of All Disease Cluster Shapes
     Shannon C. Wieland, John S. Brownstein (Harvard Medical School), Kenneth D. Mandl (Harvard Medical School) & Bonnie Berger

Y

• Locally Decodable Codes and Private Information Retrieval Schemes
     Sergey Yekhanin