Kleinberg Complex Networks

Abstract

This is the final report for AFOSR Award FA9550-09-1-0100. The award funded a research project conducted by PI Robert Kleinberg, investigating algorithmic aspects of the theory of complex networks as they relate to learning, routing, coding, and modeling of network structure and evolution. The research yielded a broad set of discoveries. Highlights over the five years of the project include the resolution of a twenty-year-old open question relating to the traveling salesman problem, the first rigorous analysis of Schelling's segregation process (a highly influential model that had been studied for decades via simulation in the social sciences, but whose behavior had resisted rigorous mathematical analysis prior to our work), a proof of the strongest separation to date between the power of linear and non-linear network codes, and a recent award-winning paper that introduces and analyzes a model of crowdsourced learning that sheds new light on the famous "exploration-exploitation" trade-off in sequential learning.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 21, 2014
Accession Number
ADA612226

Entities

People

  • Robert D. Kleinberg

Organizations

  • Cornell University

Tags

Communities of Interest

  • Autonomy
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Air Force Research Laboratories
  • Algorithms
  • Computational Science
  • Computer Programming
  • Differential Equations
  • Engineering
  • Linear Programming
  • Machine Learning
  • Mathematical Analysis
  • Mathematical Models
  • Models
  • Network Science
  • Optimization
  • Social Networks
  • Social Sciences
  • Students
  • Supervised Machine Learning

Readers

  • Agent-Based Social Robotics and Mobile-Assisted Learning in Virtual Environments.
  • Operations Research
  • Research Science/Academic Research