default search action
Alexander A. Sherstov
Person information
- affiliation: University of California, Los Angeles, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2023
- [j32]Alexander A. Sherstov
, Andrey A. Storozhenko, Pei Wu:
An Optimal Separation of Randomized and Quantum Query Complexity. SIAM J. Comput. 52(2): 525-567 (2023) - 2022
- [c31]Alexander A. Sherstov:
The approximate degree of DNF and CNF formulas. STOC 2022: 1194-1207 - [i43]Alexander A. Sherstov:
The Approximate Degree of DNF and CNF Formulas. CoRR abs/2209.01584 (2022) - [i42]Alexander A. Sherstov:
The Approximate Degree of DNF and CNF Formulas. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [j31]Alexander A. Sherstov:
The hardest halfspace. Comput. Complex. 30(2): 11 (2021) - [j30]Aleksandrs Belovs, Arturo Castellanos, Francois Le Gall, Guillaume Malod, Alexander A. Sherstov:
Quantum communication complexity of distribution testing. Quantum Inf. Comput. 21(15&16): 1261-1273 (2021) - [c30]Alexander A. Sherstov
An optimal separation of randomized and Quantum query complexity. STOC 2021: 1289-1302 - 2020
- [j29]Alexander A. Sherstov
Algorithmic Polynomials. SIAM J. Comput. 49(6): 1173-1231 (2020) - [j28]Vladimir V. Podolskii
Inner Product and Set Disjointness: Beyond Logarithmically Many Parties. ACM Trans. Comput. Theory 12(4): 26:1-26:28 (2020) - [i41]Aleksandrs Belovs, Arturo Castellanos, François Le Gall, Guillaume Malod, Alexander A. Sherstov:
Quantum Communication Complexity of Distribution Testing. CoRR abs/2006.14870 (2020) - [i40]Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu:
An Optimal Separation of Randomized and Quantum Query Complexity. CoRR abs/2008.10223 (2020) - [i39]Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu:
An Optimal Separation of Randomized and Quantum Query Complexity. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [j27]Alexander A. Sherstov
Optimal Interactive Coding for Insertions, Deletions, and Substitutions. IEEE Trans. Inf. Theory 65(10): 5971-6000 (2019) - [c29]Alexander A. Sherstov, Pei Wu:
Near-optimal lower bounds on the threshold degree and sign-rank of AC0. STOC 2019: 401-412 - [i38]Alexander A. Sherstov, Pei Wu:
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0. CoRR abs/1901.00988 (2019) - [i37]Alexander A. Sherstov:
The Hardest Halfspace. CoRR abs/1902.01765 (2019) - [i36]Alexander A. Sherstov, Justin Thaler:
Vanishing-Error Approximate Degree and QMA Complexity. CoRR abs/1909.07498 (2019) - [i35]Alexander A. Sherstov:
The hardest halfspace. Electron. Colloquium Comput. Complex. TR19 (2019) - [i34]Alexander A. Sherstov, Justin Thaler:
Vanishing-Error Approximate Degree and QMA Complexity. Electron. Colloquium Comput. Complex. TR19 (2019) - [i33]Alexander A. Sherstov, Pei Wu:
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [j26]Alexander A. Sherstov:
Compressing Interactive Communication Under Product Distributions. SIAM J. Comput. 47(2): 367-419 (2018) - [j25]Alexander A. Sherstov:
Breaking the Minsky-Papert Barrier for Constant-Depth Circuits. SIAM J. Comput. 47(5): 1809-1857 (2018) - [j24]Alexander A. Sherstov:
The Power of Asymmetry in Constant-Depth Circuits. SIAM J. Comput. 47(6): 2362-2434 (2018) - [j23]Alexander A. Sherstov:
On Multiparty Communication with Large versus Unbounded Error. Theory Comput. 14(1): 1-17 (2018) - [c28]Alexander A. Sherstov:
Algorithmic polynomials. STOC 2018: 311-324 - [i32]Alexander A. Sherstov:
Algorithmic Polynomials. CoRR abs/1801.04607 (2018) - [i31]Alexander A. Sherstov:
Algorithmic polynomials. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [c27]Alexander A. Sherstov, Pei Wu:
Optimal Interactive Coding for Insertions, Deletions, and Substitutions. FOCS 2017: 240-251 - [i30]Vladimir V. Podolskii, Alexander A. Sherstov:
Inner Product and Set Disjointness: Beyond Logarithmically Many Parties. CoRR abs/1711.10661 (2017) - [i29]Vladimir V. Podolskii, Alexander A. Sherstov:
Inner Product and Set Disjointness: Beyond Logarithmically Many Parties. Electron. Colloquium Comput. Complex. TR17 (2017) - [i28]Alexander A. Sherstov, Pei Wu:
Optimal Interactive Coding for Insertions, Deletions, and Substitutions. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j22]Alexander A. Sherstov:
The Multiparty Communication Complexity of Set Disjointness. SIAM J. Comput. 45(4): 1450-1489 (2016) - [c26]Vipul Goyal, Yuval Ishai, Hemanta K. Maji, Amit Sahai, Alexander A. Sherstov:
Bounded-Communication Leakage Resilience via Parity-Resilient Circuits. FOCS 2016: 1-10 - [c25]Alexander A. Sherstov:
Compressing Interactive Communication under Product Distributions. FOCS 2016: 535-544 - [i27]Alexander A. Sherstov:
Compressing interactive communication under product distributions. Electron. Colloquium Comput. Complex. TR16 (2016) - [i26]Alexander A. Sherstov:
On multiparty communication with large versus unbounded error. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [c24]Alexander A. Sherstov:
The Power of Asymmetry in Constant-Depth Circuits. FOCS 2015: 431-450 - [i25]Alexander A. Sherstov:
The Power of Asymmetry in Constant-Depth Circuits. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j21]Alexander A. Sherstov:
Communication Lower Bounds Using Directional Derivatives. J. ACM 61(6): 34:1-34:71 (2014) - [c23]Alexander A. Sherstov:
Communication Complexity Theory: Thirty-Five Years of Set Disjointness. MFCS (1) 2014: 24-43 - [c22]Alexander A. Sherstov:
Breaking the minsky-papert barrier for constant-depth circuits. STOC 2014: 223-232 - [i24]Alexander A. Sherstov:
Breaking the Minsky-Papert Barrier for Constant-Depth Circuits. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [j20]Alexander A. Sherstov:
Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. Comb. 33(1): 73-96 (2013) - [j19]Alexander A. Sherstov:
The Intersection of Two Halfspaces Has High Threshold Degree. SIAM J. Comput. 42(6): 2329-2374 (2013) - [j18]Alexander A. Sherstov:
Making Polynomials Robust to Noise. Theory Comput. 9: 593-615 (2013) - [j17]Alexander A. Sherstov:
Approximating the AND-OR Tree. Theory Comput. 9: 653-663 (2013) - [c21]Alexander A. Sherstov:
Communication lower bounds using directional derivatives. STOC 2013: 921-930 - [i23]Alexander A. Sherstov:
Communication Lower Bounds Using Directional Derivatives. Electron. Colloquium Comput. Complex. TR13 (2013) - [i22]Alexander A. Sherstov:
Approximating the AND-OR Tree. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j16]Alexander A. Sherstov:
Strong Direct Product Theorems for Quantum Communication and Query Complexity. SIAM J. Comput. 41(5): 1122-1165 (2012) - [j15]Alexander A. Sherstov:
The Communication Complexity of Gap Hamming Distance. Theory Comput. 8(1): 197-208 (2012) - [c20]Alexander A. Sherstov:
The multiparty communication complexity of set disjointness. STOC 2012: 525-548 - [c19]Alexander A. Sherstov:
Making polynomials robust to noise. STOC 2012: 747-758 - [i21]Alexander A. Sherstov:
Making Polynomials Robust to Noise. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [j14]Alexander A. Sherstov:
The unbounded-error communication complexity of symmetric functions. Comb. 31(5): 583-614 (2011) - [j13]Alexander A. Sherstov:
The Pattern Matrix Method. SIAM J. Comput. 40(6): 1969-2000 (2011) - [c18]Alexander A. Sherstov:
Strong direct product theorems for quantum communication and query complexity. STOC 2011: 41-50 - [i20]Alexander A. Sherstov:
Strong Direct Product Theorems for Quantum Communication and Query Complexity. Electron. Colloquium Comput. Complex. TR11 (2011) - [i19]Alexander A. Sherstov:
The Communication Complexity of Gap Hamming Distance. Electron. Colloquium Comput. Complex. TR11 (2011) - [i18]Alexander A. Sherstov:
The Multiparty Communication Complexity of Set Disjointness. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [j12]Alexander A. Sherstov:
Communication Complexity Under Product and Nonproduct Distributions. Comput. Complex. 19(1): 135-150 (2010) - [j11]Adam R. Klivans, Alexander A. Sherstov:
Lower Bounds for Agnostic Learning via Approximate Rank. Comput. Complex. 19(4): 581-604 (2010) - [j10]Alexander A. Sherstov:
On quantum-classical equivalence for composed communication problems. Quantum Inf. Comput. 10(5&6): 435-455 (2010) - [j9]Alexander A. Razborov, Alexander A. Sherstov:
The Sign-Rank of AC0. SIAM J. Comput. 39(5): 1833-1855 (2010) - [j8]Dmitry Gavinsky, Alexander A. Sherstov:
A Separation of NP and coNP in Multiparty Communication Complexity. Theory Comput. 6(1): 227-245 (2010) - [c17]Alexander A. Sherstov:
Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. STOC 2010: 523-532 - [i17]Dmitry Gavinsky, Alexander A. Sherstov:
A Separation of NP and coNP in Multiparty Communication Complexity. CoRR abs/1004.0817 (2010) - [i16]Alexander A. Sherstov:
Strong direct product theorems for quantum communication and query complexity. CoRR abs/1011.4935 (2010) - [i15]Dmitry Gavinsky, Alexander A. Sherstov:
A Separation of NP and coNP in Multiparty Communication Complexity. Electron. Colloquium Comput. Complex. TR10 (2010) - [i14]Alexander A. Sherstov:
Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [j7]Alexander A. Sherstov:
Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions. Comput. Complex. 18(2): 219-247 (2009) - [j6]Adam R. Klivans, Alexander A. Sherstov:
Cryptographic hardness for learning intersections of halfspaces. J. Comput. Syst. Sci. 75(1): 2-12 (2009) - [j5]Alexander A. Sherstov:
SeparatingAC0 from Depth-2 Majority Circuits. SIAM J. Comput. 38(6): 2113-2129 (2009) - [c16]Alexander A. Sherstov:
The Intersection of Two Halfspaces Has High Threshold Degree. FOCS 2009: 343-362 - [i13]Alexander A. Sherstov:
On Quantum-Classical Equivalence for Composed Communication Problems. CoRR abs/0906.1399 (2009) - [i12]Alexander A. Sherstov:
The Pattern Matrix Method (Journal Version). CoRR abs/0906.4291 (2009) - [i11]Alexander A. Sherstov:
The intersection of two halfspaces has high threshold degree. CoRR abs/0910.1862 (2009) - [i10]Alexander A. Sherstov:
Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. CoRR abs/0910.4224 (2009) - [i9]Alexander A. Sherstov:
The intersection of two halfspaces has high threshold degree. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [j4]Alexander A. Sherstov:
Halfspace Matrices. Comput. Complex. 17(2): 149-178 (2008) - [j3]Alexander A. Sherstov:
Communication Lower Bounds Using Dual Polynomials. Bull. EATCS 95: 59-93 (2008) - [c15]Alexander A. Sherstov:
Communication Complexity under Product and Nonproduct Distributions. CCC 2008: 64-70 - [c14]Alexander A. Sherstov:
Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions. CCC 2008: 112-123 - [c13]Alexander A. Razborov, Alexander A. Sherstov:
The Sign-Rank of AC^O. FOCS 2008: 57-66 - [c12]Alexander A. Sherstov:
The Unbounded-Error Communication Complexity of Symmetric Functions. FOCS 2008: 384-393 - [c11]Alexander A. Sherstov:
The pattern matrix method for lower bounds on quantum communication. STOC 2008: 85-94 - [i8]Alexander A. Sherstov:
Communication Lower Bounds Using Dual Polynomials. CoRR abs/0805.2135 (2008) - [i7]Alexander A. Razborov, Alexander A. Sherstov:
The Sign-Rank of AC^0. Electron. Colloquium Comput. Complex. TR08 (2008) - [i6]Alexander A. Sherstov:
Communication Lower Bounds Using Dual Polynomials. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [j2]Alexander A. Sherstov:
Powering requires threshold depth 3. Inf. Process. Lett. 102(2-3): 104-107 (2007) - [j1]Adam R. Klivans, Alexander A. Sherstov:
Unconditional lower bounds for learning intersections of halfspaces. Mach. Learn. 69(2-3): 97-114 (2007) - [c10]Alexander A. Sherstov:
Halfspace Matrices. CCC 2007: 83-95 - [c9]Adam R. Klivans, Alexander A. Sherstov:
A Lower Bound for Agnostically Learning Disjunctions. COLT 2007: 409-423 - [c8]Alexander A. Sherstov:
Separating AC0 from depth-2 majority circuits. STOC 2007: 294-301 - [i5]Alexander A. Sherstov:
Communication Complexity under Product and Nonproduct Distributions. Electron. Colloquium Comput. Complex. TR07 (2007) - [i4]Alexander A. Sherstov:
The Pattern Matrix Method for Lower Bounds on Quantum Communication. Electron. Colloquium Comput. Complex. TR07 (2007) - [i3]Alexander A. Sherstov:
Unbounded-Error Communication Complexity of Symmetric Functions. Electron. Colloquium Comput. Complex. TR07 (2007) - [i2]Alexander A. Sherstov:
Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [c7]Adam R. Klivans, Alexander A. Sherstov:
Improved Lower Bounds for Learning Intersections of Halfspaces. COLT 2006: 335-349 - [c6]Adam R. Klivans, Alexander A. Sherstov:
Cryptographic Hardness for Learning Intersections of Halfspaces. FOCS 2006: 553-562 - [i1]Adam R. Klivans, Alexander A. Sherstov:
Cryptographic Hardness Results for Learning Intersections of Halfspaces. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [c5]Alexander A. Sherstov, Peter Stone:
Improving Action Selection in MDP's via Knowledge Transfer. AAAI 2005: 1024-1029 - [c4]Alexander A. Sherstov, Peter Stone:
Function Approximation via Tile Coding: Automating Parameter Choice. SARA 2005: 194-205 - 2004
- [c3]Alexander A. Sherstov, Peter Stone:
Three Automated Stock-Trading Agents: A Comparative Study. AMEC 2004: 173-187 - 2003
- [c2]Alexander A. Sherstov:
Distributed visualization of graph algorithms. SIGCSE 2003: 376-380 - 2002
- [c1]Michael J. Jipping, Steve Marlowe, Alexander A. Sherstov:
Using Java to design and test hardware circuits over a classroom network. SIGCSE 2002: 162-166
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-04-25 05:48 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: