BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Alexander A. Sherstov contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We prove that NP differs from coNP and coNP is not a subset of MA in the number-on-forehead model of multiparty communication complexity for up to k = (1-ε)log(n) players, where ε>0 is any constant. Specifically, we construct a function F with co-nondeterministic complexity O(log(n)) and Merlin-Arthur complexity n^{Ω(1)}. The problem was open for k > 2.
An open problem in communication complexity proposed by several authors is to prove that for every Boolean function f, the task of computing f(x AND y) has polynomially related classical and quantum bounded-error complexities. We solve a variant of this question. For every f, we prove that the task of computing, on input x and y, both of the quantities f(x AND y) and f(x OR y) has polynomially related classical and quantum bounded-error complexities. We further show that the quantum bounded-error complexity is polynomially related to the classical deterministic complexity and the block sensitivity of f. This result holds regardless of prior entanglement.
The threshold degree of a function f:{0,1}^n->{-1,+1} is the least degree of a real polynomial p with f(x)=sgn p(x). We prove that the intersection of two halfspaces on {0,1}^n has threshold degree Omega(n), which matches the trivial upper bound and completely answers a question due to Klivans (2002). The best previous lower bound was Omega(sqrt n). Our result shows that the intersection of two halfspaces on {0,1}^n only admits a trivial 2^{Theta(n)}-time learning algorithm based on sign-representation by polynomials, unlike the advances achieved in PAC learning DNF formulas and read-once Boolean formulas. The proof introduces a new technique of independent interest, based on Fourier analysis and matrix theory.
A strong direct product theorem (SDPT) states that solving n instances of a problem requires Omega(n) times the resources for a single instance, even to achieve success probability exp(-Omega(n)). We prove that quantum communication complexity obeys an SDPT whenever the communication lower bound for a single instance is proved by the generalized discrepancy method, the strongest technique in that model. We prove that quantum query complexity obeys an SDPT whenever the query lower bound for a single instance is proved by the polynomial method, one of the two main techniques in that model. In both models, we prove the corresponding XOR lemmas and threshold direct product theorems.