Noah Singer

According to our database, Noah Singer authored at least 9 papers between 2021 and 2024.

Collaborative distances:

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

2024

Streaming approximation resistance of every ordering CSP.

Noah G. Singer, Madhu Sudan, Santhoshini Velusamy

Comput. Complex., June, 2024

2023

On streaming approximation algorithms for constraint satisfaction problems.

Noah G. Singer

CoRR, 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

Streaming complexity of CSPs with randomly ordered constraints.

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

Electron. Colloquium Comput. Complex., 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