Search

Author:

Jha, Madhav

Title:

Lower Bounds for Local Monotonicity Reconstruction from Transitive Closure Spanners

Graduate Program:

Computer Science and Engineering

Keywords:

Hypercube
Property Testing
Property Reconstruction
Monotone Functions
Spanners
Hypergrid

File:

Download MadhavMS-Thesis.pdf

Committee Members:

Sofya Raskhodnikova, Thesis Advisor/Co-Advisor
Sofya Raskhodnikova, Thesis Advisor/Co-Advisor

Author:

Li, Zhenyao

Title:

Greedy Algorithm for approximating maximum induced matching

Graduate Program:

Computer Science and Engineering

Keywords:

graph theory
combinatorial problem
approximation algorithms
induced matching
greedy algorithms

File:

Download ZhenyaoLIMIM.pdf

Committee Members:

Piotr Berman, Thesis Advisor/Co-Advisor
Sofya Raskhodnikova, Thesis Advisor/Co-Advisor

Author:

Baleshzar, Roksana

Title:

UNATENESS TESTING

Graduate Program:

Computer Science and Engineering

Keywords:

Sublinear-time algorithm
property testing
unateness
monotonicity

File:

Download Roksana_Baleshzar-Thesis.pdf

Committee Members:

Sofya Raskhodnikova, Thesis Advisor/Co-Advisor
Paul Medvedev, Committee Member