Alexander A. Sherstov

Andrey A. Storozhenko

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

2022

The approximate degree of DNF and CNF formulas.

[BibT_eX]

[DOI]

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

2021

Quantum communication complexity of distribution testing.

[BibT_eX]

[DOI]

Quantum Inf. Comput., 2021

The hardest halfspace.

[BibT_eX]

[DOI]

Comput. Complex., 2021

An optimal separation of randomized and Quantum query complexity.

[BibT_eX]

[DOI]

Andrey A. Storozhenko

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

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

Algorithmic polynomials.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

2017

Inner Product and Set Disjointness: Beyond Logarithmically Many Parties.

[BibT_eX]

[DOI]

Vladimir V. Podolskii

Electron. Colloquium Comput. Complex., 2017

Optimal Interactive Coding for Insertions, Deletions, and Substitutions.

[BibT_eX]

[DOI]

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

On multiparty communication with large versus unbounded error.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Compressing Interactive Communication under Product Distributions.

[BibT_eX]

[DOI]

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 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

2015

The Power of Asymmetry in Constant-Depth Circuits.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

Breaking the minsky-papert barrier for constant-depth circuits.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

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

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

2013

Approximating the AND-OR Tree.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Communication lower bounds using directional derivatives.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing Conference, 2013

2012

Making polynomials robust to noise.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

The multiparty communication complexity of set disjointness.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 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

Strong direct product theorems for quantum communication and query complexity.

[BibT_eX]

[DOI]

Proceedings of the 43rd ACM Symposium on Theory of Computing, 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

A Separation of NP and coNP in Multiparty Communication Complexity.

[BibT_eX]

[DOI]

Dmitry Gavinsky

Electron. Colloquium Comput. Complex., 2010

Lower Bounds for Agnostic Learning via Approximate Rank.

[BibT_eX]

[DOI]

Comput. Complex., 2010

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

[BibT_eX]

[DOI]

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

2009

SeparatingAC0 from Depth-2 Majority Circuits.

[BibT_eX]

[DOI]

SIAM J. Comput., 2009

The Pattern Matrix Method (Journal Version)

[BibT_eX]

[DOI]

CoRR, 2009

The Intersection of Two Halfspaces Has High Threshold Degree.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 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

The pattern matrix method for lower bounds on quantum communication.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

The Unbounded-Error Communication Complexity of Symmetric Functions.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 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

Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions.

[BibT_eX]

[DOI]

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

Communication Complexity under Product and Nonproduct Distributions.

[BibT_eX]

[DOI]

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 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

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

Halfspace Matrices.

[BibT_eX]

[DOI]

Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007

2006

Cryptographic Hardness Results for Learning Intersections of Halfspaces.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Cryptographic Hardness for Learning Intersections of Halfspaces.

[BibT_eX]

[DOI]

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 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