Nithin Varma

45 papers A* 10A 6Misc 1Journal 26Unranked 1
YearRankTypeTitle / Venue / Authors
2026 A conf
Pseudodeterministic Algorithms for Minimum Cut Problems.
ITCS
Aryan Agarwala, Nithin Varma
2026 A* conf
Testing forbidden order-pattern properties on hypergrids.
SODA
Harish Chandramouleeswaran, Ilan Newman, Tomer Pelleg, Nithin Varma
2025 A* conf
(Almost Full) EFX for Three (and More) Types of Agents.
AAAI
Pratik Ghosal, Vishwa Prakash HV, Prajakta Nimbhorkar, Nithin Varma
2025 A* conf
EFX Exists for Three Types of Agents.
EC
Vishwa Prakash HV, Pratik Ghosal, Prajakta Nimbhorkar, Nithin Varma
2025 J jnl
Pseudodeterministic Algorithms for Minimum Cut Problems.
CoRR
Aryan Agarwala, Nithin Varma
2025 A* conf
Sublinear Data Structures for Nearest Neighbor in Ultra High Dimensions.
SoCG
Martin G. Herold, Danupon Nanongkai, Joachim Spoerhase, Nithin Varma, Zihang Wu
2025 J jnl
Sublinear Data Structures for Nearest Neighbor in Ultra High Dimensions.
CoRR
Martin G. Herold, Danupon Nanongkai, Joachim Spoerhase, Nithin Varma, Zihang Wu
2025 J jnl
Testing forbidden order-pattern properties on hypergrids.
CoRR
Harish Chandramouleeswaran, Ilan Newman, Tomer Pelleg, Nithin Varma
2025 A* conf
Towards Better-than-2 Approximation for Constrained Correlation Clustering.
ICML
Andreas Kalavas, Evangelos Kipouridis, Nithin Varma
2024 J jnl
EFX Exists for Three Types of Agents.
CoRR
Vishwa Prakash HV, Pratik Ghosal, Prajakta Nimbhorkar, Nithin Varma
2024 J jnl
Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists).
CoRR
Noga Ron-Zewi, Ronen Shaltiel, Nithin Varma
2024 J jnl
Strongly Sublinear Algorithms for Testing Pattern Freeness.
TheoretiCS
Ilan Newman, Nithin Varma
2023 J jnl
Average Sensitivity of Graph Algorithms.
SIAM J. Comput.
Nithin Varma, Yuichi Yoshida
2023 J jnl
EFX Exists for Four Agents with Three Types of Valuations.
CoRR
Pratik Ghosal, Vishwa Prakash HV, Prajakta Nimbhorkar, Nithin Varma
2023 J jnl
Sublinear-Time Computation in the Presence of Online Erasures.
Theory Comput.
Iden Kalemaj, Sofya Raskhodnikova, Nithin Varma
2022 J jnl
Erasure-Resilient Sublinear-Time Graph Algorithms.
ACM Trans. Comput. Theory
Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma
2022 — conf
Parameterized Convexity Testing.
SOSA
Abhiruk Lahiri, Ilan Newman, Nithin Varma
2022 A* conf
Strongly Sublinear Algorithms for Testing Pattern Freeness.
ICALP
Ilan Newman, Nithin Varma
2022 A conf
Sublinear-Time Computation in the Presence of Online Erasures.
ITCS
Iden Kalemaj, Sofya Raskhodnikova, Nithin Varma
2021 A* conf
Average Sensitivity of Graph Algorithms.
SODA
Nithin Varma, Yuichi Yoshida
2021 A conf
Erasure-Resilient Sublinear-Time Graph Algorithms.
ITCS
Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma
2021 J jnl
Erasures versus errors in local decoding and property testing.
Random Struct. Algorithms
Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma
2021 A* conf
New Sublinear Algorithms and Lower Bounds for LIS Estimation.
ICALP
Ilan Newman, Nithin Varma
2021 J jnl
Parameterized Convexity Testing.
CoRR
Abhiruk Lahiri, Ilan Newman, Nithin Varma
2021 A conf
Query Complexity Lower Bounds for Local List-Decoding and Hard-Core Predicates (Even for Small Rate and Huge Lists).
ITCS
Noga Ron-Zewi, Ronen Shaltiel, Nithin Varma
2021 J jnl
Strongly Sublinear Algorithms for Testing Pattern Freeness.
CoRR
Ilan Newman, Nithin Varma
2021 J jnl
Sublinear-Time Computation in the Presence of Online Erasures.
CoRR
Iden Kalemaj, Sofya Raskhodnikova, Nithin Varma
2020 J jnl
Bipartite graphs of small readability.
Theor. Comput. Sci.
Rayan Chikhi, Vladan Jovicic, Stefan Kratsch, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova, Nithin Varma
2020 J jnl
Erasure-Resilient Sublinear-Time Graph Algorithms.
CoRR
Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma
2020 J jnl
Erasure-Resilient Sublinear-Time Graph Algorithms.
Electron. Colloquium Comput. Complex.
Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma
2020 J jnl
New Algorithms and Lower Bounds for LIS Estimation.
CoRR
Ilan Newman, Nithin Varma
2020 J jnl
Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists).
Electron. Colloquium Comput. Complex.
Noga Ron-Zewi, Ronen Shaltiel, Nithin Varma
2019 — —
Analyzing massive datasets with missing entries: models and algorithms
Nithin Varma
2019 J jnl
Average Sensitivity of Graph Algorithms.
CoRR
Nithin Varma, Yuichi Yoshida
2019 A conf
Erasures vs. Errors in Local Decoding and Property Testing.
ITCS
Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma
2018 Misc conf
Bipartite Graphs of Small Readability.
COCOON
Rayan Chikhi, Vladan Jovicic, Stefan Kratsch, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova, Nithin Varma
2018 J jnl
Bipartite Graphs of Small Readability.
CoRR
Rayan Chikhi, Vladan Jovicic, Stefan Kratsch, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova, Nithin Varma
2018 A* conf
Brief Announcement: Erasure-Resilience Versus Tolerance to Errors.
ICALP
Sofya Raskhodnikova, Nithin Varma
2018 J jnl
Erasure-Resilient Property Testing.
SIAM J. Comput.
Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, Nithin Varma
2018 J jnl
Erasures versus Errors in Local Decoding and Property Testing.
Electron. Colloquium Comput. Complex.
Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma
2018 J jnl
Parameterized Property Testing of Functions.
ACM Trans. Comput. Theory
Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma
2017 A conf
Parameterized Property Testing of Functions.
ITCS
Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma
2017 J jnl
Parameterized Property Testing of Functions.
Electron. Colloquium Comput. Complex.
Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma
2016 A* conf
Erasure-Resilient Property Testing.
ICALP
Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, Nithin Varma
2016 J jnl
Erasure-Resilient Property Testing.
CoRR
Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, Nithin Varma