Noah Singer

According to our database, Noah Singer authored at least 16 papers between 2021 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

Sketching approximations and LP approximations for finite CSPs are related.

Noah G. Singer, Madhur Tulsiani, Santhoshini Velusamy

CoRR, September, 2025

A Classical Quadratic Speedup for Planted <i>k</i>XOR.

Meghal Gupta, William He, Ryan O'Donnell, Noah G. Singer

CoRR, August, 2025

Streaming Algorithms via Local Algorithms for Maximum Directed Cut.

Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, Santhoshini Velusamy

Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025

Algebra Is Half the Battle: Verifying Presentations of Graded Unipotent Chevalley Groups.

Eric Wang, Arohee Bhoja, Cayden R. Codel, Noah G. Singer

Proceedings of the 16th International Conference on Interactive Theorem Proving, 2025

Latency Guarantees for Caching with Delayed Hits.

Keerthana Gurushankar, Noah G. Singer, Bernardo Subercaseaux

Proceedings of the IEEE INFOCOM 2025, 2025

2024

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds.

Samuel Hwang, Noah G. Singer, Santhoshini Velusamy

CoRR, 2024

Coboundary expansion inside Chevalley coset complex HDXs.

Ryan O'Donnell, Noah G. Singer

CoRR, 2024

2023

On streaming approximation algorithms for constraint satisfaction problems.

Noah G. Singer

CoRR, 2023

Streaming complexity of CSPs with randomly ordered constraints.

Raghuvansh R. Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots.

Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, Santhoshini Velusamy

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Oblivious Algorithms for the Max-kAND Problem.

Noah G. Singer

Proceedings of the Approximation, 2023

2022

Point-hyperplane Incidence Geometry and the Log-rank Conjecture.

Noah Singer, Madhu Sudan

ACM Trans. Comput. Theory, 2022

Streaming beyond sketching for Maximum Directed Cut.

Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy

Electron. Colloquium Comput. Complex., 2022

On Sketching Approximations for Symmetric Boolean CSPs.

Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, Santhoshini Velusamy

Proceedings of the Approximation, 2022

2021

Closed-form expressions for the sketching approximability of (some) symmetric Boolean CSPs.

Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, Santhoshini Velusamy

CoRR, 2021

Streaming Approximation Resistance of Every Ordering CSP.

Noah Singer, Madhu Sudan, Santhoshini Velusamy

Proceedings of the Approximation, 2021