The Library
Tolerant bipartiteness testing in dense graphs
Tools
Tools
Tools
Ghosh, Arijit, Mishra, Gopinath, Raychaudhury, Rahul and Sen, Sayantan (2022) Tolerant bipartiteness testing in dense graphs. In: The 49th EATCS International Colloquium on Automata, Languages and Programming (ICALP), Paris, France, 4-8 Jul 2022. Published in: Leibniz International Proceedings in Informatics (LIPIcs), 229 69:1-69:19. ISBN 9783959772358. ISSN 1868-8969. doi:10.4230/LIPIcs.ICALP.2022
|
PDF
WRAP-tolerant-bipartiteness-testing-dense-graphs-Mishra-2022.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (842Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.ICALP.2022
Abstract
Bipartite testing has been a central problem in the area of property testing since its inception in the seminal work of Goldreich, Goldwasser, and Ron.
Though the non-tolerant version of bipartite testing has been extensively studied in the literature, the tolerant variant is not well understood. In this paper, we consider the following version of the tolerant bipartite testing problem:
Given two parameters $\varepsilon, \delta \in (0,1)$, with $\delta > \varepsilon$, and access to the adjacency matrix of a graph $G$, we have to decide whether $G$ can be made bipartite by editing at most $\varepsilon n^2$ entries of the adjacency matrix of $G$, or we have to edit at least $\delta n^2$ entries of the adjacency matrix to make $G$ bipartite. In this paper, we prove that for $\delta=(2+\Omega(1))\varepsilon$, tolerant bipartite testing can be decided by performing $\widetilde{\mathcal{O}}\left({1}/{\varepsilon ^3}\right)$ many adjacency queries and in $2^{\widetilde{\mathcal{O}}(1/\varepsilon)}$ time complexity. This improves upon the state-of-the-art query and time complexities of this problem of $\widetilde{\mathcal{O}}\left({1}/{\varepsilon ^6}\right)$ and $2^{\widetilde{\mathcal{O}}(1/\varepsilon^2)}$, respectively, due to
Alon, Fernandez de la Vega, Kannan and Karpinski,
where $\widetilde{\mathcal{O}}(\cdot)$ hides a factor polynomial in $\log \left({1}/{\varepsilon}\right)$.
| Item Type: | Conference Item (Paper) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA75 (Please use QA76 Electronic Computers. Computer Science) Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
|||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science Faculty of Science, Engineering and Medicine > Science > Mathematics |
|||||||||
| Library of Congress Subject Headings (LCSH): | Bipartite graphs, Machine theory, Computational complexity, Linear systems | |||||||||
| Journal or Publication Title: | Leibniz International Proceedings in Informatics (LIPIcs) | |||||||||
| Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | |||||||||
| ISBN: | 9783959772358 | |||||||||
| ISSN: | 1868-8969 | |||||||||
| Official Date: | 2022 | |||||||||
| Dates: |
|
|||||||||
| Volume: | 229 | |||||||||
| Page Range: | 69:1-69:19 | |||||||||
| Article Number: | 69 | |||||||||
| DOI: | 10.4230/LIPIcs.ICALP.2022 | |||||||||
| Status: | Peer Reviewed | |||||||||
| Publication Status: | Published | |||||||||
| Access rights to Published version: | Open Access | |||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||
| Conference Paper Type: | Paper | |||||||||
| Title of Event: | The 49th EATCS International Colloquium on Automata, Languages and Programming (ICALP) | |||||||||
| Type of Event: | Conference | |||||||||
| Location of Event: | Paris, France | |||||||||
| Date(s) of Event: | 4-8 Jul 2022 | |||||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
