Nitin Saurabh

According to our database1, Nitin Saurabh authored at least 21 papers between 2012 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

On csauthors.net:

Bibliography

2024
On the Communication Complexity of Finding a King in a Tournament.
Proceedings of the Approximation, 2024

Approximate Degree Composition for Recursive Functions.
Proceedings of the Approximation, 2024

2023
On the Composition of Randomized Query Complexity and Approximate Degree.
Electron. Colloquium Comput. Complex., 2023

Randomized and Quantum Query Complexities of Finding a King in a Tournament.
Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023

2022
Approximate polymorphisms.
Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Rabbits Approximate, Cows Compute Exactly!
Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, 2022

Tight Lower Bounds for Approximate & Exact k-Center in ℝ<sup>d</sup>.
Proceedings of the 38th International Symposium on Computational Geometry, 2022

2021
Karchmer-Wigderson Games for Hazard-free Computation.
Electron. Colloquium Comput. Complex., 2021

2020
On the complexity of detecting hazards.
Inf. Process. Lett., 2020

Algebraic Branching Programs, Border Complexity, and Tangent Spaces.
Electron. Colloquium Comput. Complex., 2020

Lower bounds for linear decision lists.
Chic. J. Theor. Comput. Sci., 2020

2018
Improved bounds on Fourier entropy and Min-entropy.
Electron. Colloquium Comput. Complex., 2018

Fourier Entropy-Influence Conjecture for Random Linear Threshold Functions.
Proceedings of the LATIN 2018: Theoretical Informatics, 2018

Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity.
Proceedings of the 26th Annual European Symposium on Algorithms, 2018

2017
Optimal Quasi-Gray Codes: Does the Alphabet Matter?
CoRR, 2017

2016
Upper bounds on Fourier entropy.
Theor. Comput. Sci., 2016

VNP=VP in the multilinear world.
Inf. Process. Lett., 2016

Some Complete and Intermediate Polynomials in Algebraic Complexity Theory.
Electron. Colloquium Comput. Complex., 2016

Homomorphism Polynomials Complete for VP.
Chic. J. Theor. Comput. Sci., 2016

2013
An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas.
Electron. Colloquium Comput. Complex., 2013

2012
Counting paths in planar width 2 branching programs.
Proceedings of the Eighteenth Computing: The Australasian Theory Symposium, 2012


  Loading...