Back to search

Cornell University

Solving network problems by embedding discrete structure in continuous space

Abstract

dc:description.abstract

Many problems can be formulated as questions about networks. We introduce a general strategy for embedding such problems in Euclidean space and finding discrete solutions in this space, with examples in the Boolean satisfiability (3-SAT) problem, the problem of finding a dominating set of a network, and the problem of encoding a binary data set as the output of a Boolean generative network. Then we introduce a novel directed percolation inverse problem, provide an algorithm for solving it, and investigate how the time it takes to find a solution is related to the percolation properties of the network. Next, we find a compact network representation of movie and viewer attributes from a set of Netflix users' ratings (useful for predicting whether a viewer will like a movie they have not seen). Our approach can match the performance of similar methods but requires far fewer attributes and only a fraction of the training data. Finally, we turn to natural language processing, where the most impressive recent results come from deep neural networks with hundreds of billions of continuous parameters. These networks are too complicated for humans to interpret and require mountains of training data, making it difficult to diagnose and correct unwanted behavior. We demonstrate two approaches that embrace the discreteness of syntax in order to learn grammar from a hundred or even fewer training sentences, produce interpretable output of their inferences, and generate novel sentences from the inferred grammar in a transparent way.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Physics
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Physics
Grantor
Cornell University
Year dc:date.issued
2023

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Deyo, Sean
Chair dc:contributor.chair
  • Elser, Veit
Committee members dc:contributor.committeemember
  • Sethna, James
  • McEuen, Paul

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
16176432
Dc Identifier Other
ProQuest Submission ID: 13611
ProQuest Publication ID: 30484818

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Deyo, Sean. Solving network problems by embedding discrete structure in continuous space. Doctor of Philosophy thesis, Cornell University, 2023. https://hdl.handle.net/1813/114020