---
author:
- |
    Soheil Behnezhad[^1]\
    <span>*Stanford University*</span>
bibliography:
- 'references.bib'
title: |
    Time-Optimal Sublinear Algorithms for\
    Matching and Vertex Cover[^2]
---

Introduction {#sec:intro}
============

Average Query-Complexity of RGMM {#sec:query}
================================

The Final Algorithms for the Adjacency List Query Model {#sec:adjlist}
=======================================================

The Final Algorithm for the Adjacency Matrix Query Model {#sec:adjmatrix}
========================================================

Acknowledgements
================

I thank Sanjeev Khanna for many helpful discussions, and additionally thank Yu Chen, Sanjeev Khanna, and Zihan Tan for insightful comments.

[^1]: Research was done in part while the author was funded by a Google PhD Fellowship at the University of Maryland.

[^2]: A preliminary version of this paper appeared in proceedings of FOCS 2021.

{'source': 'arXiv_out/2106'}