Page
%P
-
Article
Asymptotic Delsarte cliques in distance-regular graphs
We give a new bound on the parameter \(\lambda \) λ
-
Chapter and Conference Paper
Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups
We consider the problem of testing isomorphism of groups of order n given by Cayley tables. The trivial n logn bound on the time complexity for the general case has not been impro...
-
Chapter and Conference Paper
Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas
Finite groups have affected complexity theory and complexity theory has had an impact on computational group theory. This paper is a personal account of the author’s journey through the evolution of some of th...
-
Chapter and Conference Paper
Weights of Exact Threshold Functions
We consider Boolean exact threshold functions defined by linear equations, and in general degree d polynomials. We give upper and lower bounds on the maximum magnitude (absolute value) of the coefficients require...
-
Article
Finite groups of uniform logarithmic diameter
We demonstrate the existence of an infinite family of finite groups with 2 generators and logarithmic diameter with respect to any set of generators. This answers a question of A. Lubotzky. Moreover, in our gr...
-
Book
-
Chapter
Exercise and Delayed Preconditioning in the Protection of the Heart against Ventricular Arrhythmias: Crucial Role of Nitric Oxide
Ischaemic preconditioning results not only in a reduction in myocardial ischaemic damage but also a marked suppression of those ventricular arrhythmias that result from a prolonged period of ischaemia and repe...
-
Article
The Cost of the Missing Bit: Communication Complexity with Help
-
Article
Superpolynomial Lower Bounds for Monotone Span Programs
computing explicit functions. The best previous lower bound was by Beimel, Gál, Paterson [7]; our proof exploits a general combinatorial lower bound criterion from that paper...
-
Chapter and Conference Paper
Communication complexity
We discuss some aspects of two-party and multi-party communication complexity theory. The topics include a sample from the long list of connections of communication complexity to other models of computation wh...
-
Article
Paul Erdös 1913–1996
-
Chapter and Conference Paper
Simultaneous messages vs. communication
In the multiparty communication game introduced by Chandra, Furst, and Lipton [CFL] (1983), k players wish to evaluate collaboratively a function f(x 0,⋯, x k−1 for which player i sees all inputs except x ...
-
Chapter
Transparent Proofs and Limits to Approximation
We survey a major collective accomplishment of the theoretical computer science community on efficiently verifiable proofs.
-
Chapter and Conference Paper
Transparent (holographic) proofs
Informally, a mathematical proof is transparent (or holographic) if it can be verified with large confidence by a small number of spotchecks. Recent work of a large group of researchers has shown that this seemin...
-
Article
Tibor Gallai, 1912–1992
-
Article
Arithmetization: A new method in structural complexity theory
We introduce a technique of arithmetization of the process of computation in order to obtain novel characterizations of certain complexity classes viamultivariate polynomials. A variety of concepts and tools of e...
-
Article
Non-deterministic exponential time has two-prover interactive protocols
We determine the exact power of two-prover interactive proof systems introduced by Ben-Or, Goldwasser, Kilian, and Wigderson (1988). In this system, two all-powerful noncommunicating provers convince a randomi...
-
Article
Editors’ foreword
-
Article
Editors’ foreword
-
Article
An anti-Ramsey theorem
An edge-coloring of a graph is a partition of the set of edges into color-classes such that no two edges in the same class are adjacent. A subsetA of the vertex set isantihomogeneous if all edges in the subgraph ...
