Alexander A. Sherstov

Andrey A. Storozhenko

Electron. Colloquium Comput. Complex., 2024

2023

An Optimal Separation of Randomized and Quantum Query Complexity.

[BibT_eX]

[DOI]

Andrey A. Storozhenko

SIAM J. Comput., April, 2023

2022

The Approximate Degree of DNF and CNF Formulas.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

2021

Quantum communication complexity of distribution testing.

[BibT_eX]

[DOI]

Quantum Inf. Comput., 2021

The hardest halfspace.

[BibT_eX]

[DOI]

Comput. Complex., 2021

2020

Algorithmic Polynomials.

[BibT_eX]

[DOI]

SIAM J. Comput., 2020

2019

Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

Vanishing-Error Approximate Degree and QMA Complexity.

[BibT_eX]

[DOI]

Justin Thaler

Electron. Colloquium Comput. Complex., 2019

Near-optimal lower bounds on the threshold degree and sign-rank of AC0.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

2018

The Power of Asymmetry in Constant-Depth Circuits.

[BibT_eX]

[DOI]

SIAM J. Comput., 2018

Breaking the Minsky-Papert Barrier for Constant-Depth Circuits.

[BibT_eX]

[DOI]

SIAM J. Comput., 2018

Compressing Interactive Communication Under Product Distributions.

[BibT_eX]

[DOI]

SIAM J. Comput., 2018

2017

Optimal Interactive Coding for Insertions, Deletions, and Substitutions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Inner Product and Set Disjointness: Beyond Logarithmically Many Parties.

[BibT_eX]

[DOI]

Vladimir V. Podolskii

Electron. Colloquium Comput. Complex., 2017

2016

The Multiparty Communication Complexity of Set Disjointness.

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

On multiparty communication with large versus unbounded error.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Bounded-Communication Leakage Resilience via Parity-Resilient Circuits.

[BibT_eX]

[DOI]

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2014

Communication Complexity Theory: Thirty-Five Years of Set Disjointness.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

2013

The Intersection of Two Halfspaces Has High Threshold Degree.

[BibT_eX]

[DOI]

SIAM J. Comput., 2013

Approximating the AND-OR Tree.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Communication Lower Bounds Using Directional Derivatives.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

2012

Strong Direct Product Theorems for Quantum Communication and Query Complexity.

[BibT_eX]

[DOI]

SIAM J. Comput., 2012

Making Polynomials Robust to Noise.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

2011

The Pattern Matrix Method.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

The Communication Complexity of Gap Hamming Distance.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

2010

The Sign-Rank of AC0.

[BibT_eX]

[DOI]

Alexander A. Razborov

SIAM J. Comput., 2010

On quantum-classical equivalence for composed communication problems.

[BibT_eX]

[DOI]

Quantum Inf. Comput., 2010

Optimal bounds for sign-representing the intersection of two halfspaces by polynomials.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

A Separation of NP and coNP in Multiparty Communication Complexity.

[BibT_eX]

[DOI]

Dmitry Gavinsky

Electron. Colloquium Comput. Complex., 2010

Communication Complexity Under Product and Nonproduct Distributions.

[BibT_eX]

[DOI]

Comput. Complex., 2010

Lower Bounds for Agnostic Learning via Approximate Rank.

[BibT_eX]

[DOI]

Comput. Complex., 2010

2009

SeparatingAC0 from Depth-2 Majority Circuits.

[BibT_eX]

[DOI]

SIAM J. Comput., 2009

Cryptographic hardness for learning intersections of halfspaces.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2009

The Pattern Matrix Method (Journal Version)

[BibT_eX]

[DOI]

CoRR, 2009

Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions.

[BibT_eX]

[DOI]

Comput. Complex., 2009

2008

Communication Lower Bounds Using Dual Polynomials.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

The Sign-Rank of AC^0.

[BibT_eX]

[DOI]

Alexander A. Razborov

Electron. Colloquium Comput. Complex., 2008

Halfspace Matrices.

[BibT_eX]

[DOI]

Comput. Complex., 2008

The Sign-Rank of AC^O.

[BibT_eX]

[DOI]

Alexander A. Razborov

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

Unconditional lower bounds for learning intersections of halfspaces.

[BibT_eX]

[DOI]

Mach. Learn., 2007

Powering requires threshold depth 3.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2007

Unbounded-Error Communication Complexity of Symmetric Functions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

The Pattern Matrix Method for Lower Bounds on Quantum Communication.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

Separating AC0 from depth-2 majority circuits.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

A Lower Bound for Agnostically Learning Disjunctions.

[BibT_eX]

[DOI]

Proceedings of the Learning Theory, 20th Annual Conference on Learning Theory, 2007

2006

Cryptographic Hardness Results for Learning Intersections of Halfspaces.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Improved Lower Bounds for Learning Intersections of Halfspaces.

[BibT_eX]

[DOI]

Proceedings of the Learning Theory, 19th Annual Conference on Learning Theory, 2006

2005

Function Approximation via Tile Coding: Automating Parameter Choice.

[BibT_eX]

[DOI]

Peter Stone

Proceedings of the Abstraction, 2005

Improving Action Selection in MDP's via Knowledge Transfer.

[BibT_eX]

[DOI]

Peter Stone

Proceedings of the Proceedings, 2005

2004

Three Automated Stock-Trading Agents: A Comparative Study.

[BibT_eX]

[DOI]

Peter Stone

Proceedings of the Agent-Mediated Electronic Commerce VI, 2004

2003

Distributed visualization of graph algorithms.

[BibT_eX]

[DOI]

Proceedings of the 34th SIGCSE Technical Symposium on Computer Science Education, 2003

2002

Using Java to design and test hardware circuits over a classroom network.

[BibT_eX]

[DOI]

Michael J. Jipping

Steve Marlowe