Nitin Saurabh

List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

Publication	Date of Publication	Type
On the composition of randomized query complexity and approximate degree	2025-01-14	Paper
Karchmer-Wigderson games for hazard-free computation	2024-09-25	Paper
Rabbits approximate, cows compute Exactly!	2024-08-06	Paper
Tight lower bounds for approximate \& exact \(k\)-center in \(\mathbb{R}^d\)	2024-05-14	Paper
Approximate polymorphisms Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing	2023-12-08	Paper
Improved Bounds on Fourier Entropy and Min-Entropy	2023-02-07	Paper
scientific article; zbMATH DE number 7561749 (Why is no real title available?) (available as arXiv preprint)	2022-07-21	Paper
Improved bounds on Fourier entropy and min-entropy ACM Transactions on Computation Theory	2022-03-29	Paper
Improved bounds on Fourier entropy and min-entropy ACM Transactions on Computation Theory	2022-03-29	Paper
Space-optimal quasi-Gray codes with logarithmic read complexity	2021-08-04	Paper
Lower bounds for linear decision lists Chicago Journal of Theoretical Computer Science	2021-05-14	Paper
On the complexity of detecting hazards Information Processing Letters	2020-10-07	Paper
Fourier entropy influence conjecture for random linear threshold functions (available as arXiv preprint)	2020-02-12	Paper
Some complete and intermediate polynomials in algebraic complexity theory Theory of Computing Systems	2018-06-01	Paper
Homomorphism polynomials complete for VP	2017-04-25	Paper
Upper bounds on Fourier entropy Theoretical Computer Science	2016-11-24	Paper
An improved deterministic \#SAT algorithm for small De Morgan formulas Algorithmica	2016-11-01	Paper
Some complete and intermediate polynomials in algebraic complexity theory Lecture Notes in Computer Science	2016-07-25	Paper
Homomorphism polynomials complete for VP Chicago Journal of Theoretical Computer Science	2016-05-24	Paper
\textsf{VNP} = \textsf{VP} in the multilinear world Information Processing Letters	2015-12-01	Paper
Upper bounds on Fourier entropy Lecture Notes in Computer Science	2015-10-29	Paper
An improved deterministic \#SAT algorithm for small De Morgan formulas Mathematical Foundations of Computer Science 2014	2014-10-14	Paper

Research outcomes over time

This page was built for person: Nitin Saurabh