For a fixed positive integer \(k\), two players, \(\textsf {Builder}\) and \(\textsf {Chooser}\), alternate turns playing the following game on a dynamically changing graph that is initially empty. In each round, \(\textsf {Builder}\) introduces a new vertex with edges to all previous vertices and then partitions the entire edge set into two subsets, after which \(\textsf {Chooser}\) deletes one of the two. \(\textsf {Builder}\) attempts to build a clique of size \(k\), while \(\textsf {Chooser}\) attempts to prevent that. We prove tower-type upper and lower bounds on how many rounds \(\textsf {Builder}\) needs to guarantee a \(k\)-clique.

The extremal theory of forbidden 0-1 matrices studies the asymptotic growth of the function Ex(P, n), which is the maximum weight of a matrix A ∈ {0,1}n×n whose submatrices avoid a fixed pattern P ∈ {0, 1}k×1. This theory has been wildly successful at resolving problems in combinatorics [Kla00, MT04, CK12], discrete and computational geometry [Für90, Agg15, ES96, PS91, Mit92, BG91], structural graph theory [GM14, BGK+21, BKTW22] and the analysis of data structures [Pet10, KS20], particularly corollaries of the dynamic optimality conjecture [CGK + 15b, CGK + 15a, CGJ+23, CPY24].

Abstract. It is known that any open necklace with beads of [Formula: see text] types, in which the number of beads of each type is divisible by [Formula: see text], can be partitioned by at most [Formula: see text] cuts into intervals that can be distributed into [Formula: see text] collections, each containing the same number of beads of each type. This is tight for all values of [Formula: see text] and [Formula: see text]. Here, we consider the case of random necklaces, where the number of beads of each type is [Formula: see text]. Then the minimum number of cuts required for a “fair” partition with the above property is a random variable [Formula: see text]. We prove that for fixed [Formula: see text] and large [Formula: see text], this random variable is at least [Formula: see text] with high probability. For [Formula: see text], fixed [Formula: see text], and large [Formula: see text], we determine the asymptotic behavior of the probability that [Formula: see text] for all values of [Formula: see text]. We show that this probability is polynomially small when [Formula: see text], is bounded away from zero when [Formula: see text], and decays like [Formula: see text] when [Formula: see text]. We also show that for large [Formula: see text], [Formula: see text] is at most [Formula: see text] with high probability and that for large [Formula: see text] and large ratio [Formula: see text], [Formula: see text] is [Formula: see text] with high probability.

The disjointness graph of a set system is a graph whose vertices are the sets, two being connected by an edge if and only if they are disjoint. It is known that the disjointness graph G of any system of segments in the plane is χ-bounded, that is, its chromatic number χ(G) is upper bounded by a function of its clique number ω(G). Here we show that this statement does not remain true for systems of polygonal chains of length 2. We also construct systems of polygonal chains of length 3 such that their disjointness graphs have arbitrarily large girth and chromatic number. In the opposite direction, we show that the class of disjointness graphs of (possibly self-intersecting) 2-way infinite polygonal chains of length 3 is χ-bounded: for every such graph G, we have χ(G) ≤ (ω(G))³+ω(G).

The disjointness graph G=G(S) of a set of segments S in R^d, d>1 is a graph whose vertex set is S and two vertices are connected by an edge if and only if the corresponding segments are disjoint. We prove that the chromatic number of G satisfies chi(G)<=omega(G)^4+omega(G)^3 where omega(G) denotes the clique number of G. It follows, that S has at least cn^{1/5} pairwise intersecting or pairwise disjoint elements. Stronger bounds are established for lines in space, instead of segments. We show that computing omega(G) and chi(G) for disjointness graphs of lines in space are NP-hard tasks. However, we can design efficient algorithms to compute proper colorings of G in which the number of colors satisfies the above upper bounds. One cannot expect similar results for sets of continuous arcs, instead of segments, even in the plane. We construct families of arcs whose disjointness graphs are triangle-free (omega(G)=2), but whose chromatic numbers are arbitrarily large.

Let HDd(p, q) denote the minimal size of a transversal that can always be guaranteed for a family of compact convex sets in ℝd which satisfy the (p, q)-property (p ≥ q ≥ d + 1). In a celebrated proof of the Hadwiger-Debrunner conjecture, Alon and Kleitman proved that HDd(p, q) exists for all P ≥ q ≥ d +1. Specifically, they prove that HDd(p,d + 1) is This paper has two parts. In the first part we present several improved bounds on HDd(p, q). In particular, we obtain the first near tight estimate of HDd(p, q) for an extended range of values of (p, q) since the 1957 Hadwiger-Debrunner theorem. In the second part we prove a (p, 2)-theorem for families in ℝ2 with union complexity below a specific quadratic bound. Based on this, we introduce a polynomial time constant factor approximation algorithm for MAX-CLIQUE of intersection graphs of convex sets satisfying this property. It is not likely that our constant factor approximation can be improved to a PTAS as MAX-CLIQUE for intersection graphs of fat ellipses is known to be APX-HARD and fat ellipses have sub-quadratic union complexity.

If two closed Jordan curves in the plane have precisely one point in common, then it is called a touching point. All other intersection points are called crossing points. The main result of this paper is a Crossing Lemma for closed curves: In any family of n pairwise intersecting simple closed curves in the plane, no three of which pass through the same point, the number of crossing points exceeds the number of touching points by a factor of Ω((log log n)1/8). As a corollary, we prove the following long-standing conjecture of Richter and Thomassen: The total number of intersection points between any n pairwise intersecting simple closed curves in the plane, no three of which pass through the same point, is at least (1 – o(1))n2.

The Local Lemma is a fundamental tool of probabilistic combinatorics and theoretical computer science, yet there are hardly any natural problems known where it provides an asymptotically tight answer. The main theme of our article is to identify several of these problems, among them a couple of widely studied extremal functions related to certain restricted versions of the k -SAT problem, where the Local Lemma does give essentially optimal answers. As our main contribution, we construct unsatisfiable k -CNF formulas where every clause has k distinct literals and every variable appears in at most 2/e + o (1)) 2 k / k clauses. The Lopsided Local Lemma, applied with an assignment of random values according to counterintuitive probabilities, shows that this is asymptotically best possible. The determination of this extremal function is particularly important, as it represents the value where the corresponding k -SAT problem exhibits a complexity hardness jump: From having every instance being a YES-instance it becomes NP-hard just by allowing each variable to occur in one more clause. The construction of our unsatisfiable CNF formulas is based on the binary tree approach of Gebauer [2012], and thus the constructed formulas are in the class MU(1) of minimal unsatisfiable formulas having one more clause than variables. The main novelty of our approach here comes in setting up an appropriate continuous approximation of the problem. This leads us to a differential equation, the solution of which we are able to estimate. The asymptotically optimal binary trees are then obtained through a discretization of this solution. The importance of the binary trees constructed is also underlined by their appearance in many other scenarios. In particular, they give asymptotically precise answers for seemingly unrelated problems like the European Tenure Game introduced by Doerr [2004] and a search problem allowing a limited number of consecutive lies. As yet another consequence, we slightly improve the best-known bounds on the maximum degree and maximum edge-degree of a k -uniform Maker’s win hypergraph in the Neighborhood Conjecture of Beck.

A long standing conjecture of Richter and Thomassen states that the total number of intersection points between any n simple closed Jordan curves in the plane, so that any two of them intersect and no three curves pass through the same point, is at least (1 – o(1))n2. We confirm the above conjecture in several important cases, including the case (1) when all curves are convex, and (2) when the family of curves can be partitioned into two equal classes such that each curve from the first class is touching every curve from the second class. (Two curves are said to be touching if they have precisely one point in common, at which they do not properly cross.) An important ingredient of our proofs is the following statement: Let S be a family of the graphs of n continuous real functions defined on ℝ, no three of which pass through the same point. If there are nt pairs of touching curves in S, then the number of crossing points is .

List coloring is an NP-complete decision problem even if the total number of colors is three. It is hard even on planar bipartite graphs. We give a polynomial-time algorithm for solving list coloring of permutation graphs with a bounded total number of colors. More generally, we give a polynomial-time algorithm that solves the list-homomorphism problem to any fixed target graph for a large class of input graphs, including all permutation and interval graphs.

In this paper we study the two player randomized communication complexity of the sparse set disjointness and the exists-equal problems and give matching lower and upper bounds (up to constant factors) for any number of rounds for both of these problems. In the sparse set disjointness problem, each player receives a k-subset of [m] and the goal is to determine whether the sets intersect. For this problem, we give a protocol that communicates a total of O(k log(r)k) bits over r rounds and errs with very small probability. Here we can take r = log* k to obtain a O(k) total communication log* k-round protocol with exponentially small error probability, improving on the O(k)-bits O(log k)-round constant error probability protocol of Hastad and Wigderson from 1997. In the exists-equal problem, the players receive vectors x, y ∈ [t]nand the goal is to determine whether there exists a coordinate i such that xi= yi. Namely, the exists-equal problem is the OR of n equality problems. Observe that exists-equal is an instance of sparse set disjointness with k = n, hence the protocol above applies here as well, giving an O(n log(r)n) upper bound. Our main technical contribution in this paper is a matching lower bound: we show that when t = Ω(n), any r-round randomized protocol for the exists-equal problem with error probability at most 1/3 should have a message of size Ω(n log(r)n). Our lower bound holds even for super-constant r ≤ log* n, showing that any O(n) bits exists-equal protocol should have log* n - O(1) rounds. Note that the protocol we give errs only with less than polynomially small probability and provides guarantees on the total communication for the harder set disjointness problem, whereas our lower bound holds even for constant error probability protocols and for the easier exists-equal problem with guarantees on the max-communication. Hence our upper and lower bounds match in a strong sense. Our lower bound on the constant round protocols for exist-sequal shows that solving the OR of n instances of the equality problems requires strictly more than n times the cost of a single instance. To our knowledge this is the first example of such a super-linear increase in complexity.

We characterize obstruction sets in caterpillar dualities in terms of regular languages and give a construction of the dual of a regular family of caterpillars. In particular, we prove that every monadic linear Datalog program with at most one extensional database per rule defines the complement of a contraint satisfaction problem.

The information rate for an access structure is the reciprocal of the load of the optimal secret sharing scheme for this structure. We determine this value for all trees: it is (2-1/c)-1, wherecis the size of the largest core of the tree. A subset of the vertices of a tree is a core if it induces a connected subgraph and for each vertex in the subset one finds a neighbor outside the subset. Our result follows from a lower and an upper bound on the information rate that applies for any graph and happen to coincide for trees because of a correspondence between the size of the largest core and a quantity related to a fractional cover of the tree with stars.

According to a well known theorem of Haussler and Welzl (1987), any range space of bounded VC-dimension admits an epsilon-net of size O (1/epsilon log 1/epsilon). Using probabilistic techniques, Pach and Woeginger (1990) showed that there exist range spaces of VC-dimension 2, for which the above bound is sharp. The only known range spaces of small VC-dimension, in which the ranges are geometric objects in some Euclidean space and the size of the smallest epsilon-nets is superlinear in 1/epsilon, were found by Alon (2010). In his examples, every epsilon-net is of size Omega (1/epsilon g(1/epsilon)), where g is an extremely slowly growing function, related to the inverse Ackermann function.

In this paper, we present near-optimal space bounds for Lp-samplers. Given a stream of updates (additions and subtraction) to the coordinates of an underlying vector x in Rn, a perfect Lp sampler outputs the i-th coordinate with probability xipxpp. In SODA 2010, Monemizadeh and Woodruff showed polylog space upper bounds for approximate Lp-samplers and demonstrated various applications of them. Very recently, Andoni, Krauthgamer and Onak improved the upper bounds and gave a O(ε-plog3n) space ε relative error and constant failure rate Lp-sampler for p є [1,2]. In this work, we give another such algorithm requiring only O(ε-plog2n) space for p є (1,2). For p є (0,1), our space bound is O(ε-1log2n), while for the p=1 case we have an O(log(1/ε)ε-log2n) space algorithm. We also give a O(log2n) bits zero relative error L0-sampler, improving the O(log3n) bits algorithm due to Frahling, Indyk and Sohler.

We construct unsatisfiable k-CNF formulas where every clause has k distinct literals and every variable appears in at most clauses. The lopsided Local Lemma shows that our result is asymptotically best possible: every k-CNF formula where every variable appears in at most clauses is satisfiable. The determination of this extremal function is particularly important as it represents the value where the k-SAT problem exhibits its complexity hardness jump: from having every instance being a YES-instance it becomes NP-hard just by allowing each variable to occur in one more clause. The asymptotics of other related extremal functions are also determined. Let l(k) denote the maximum number, such that every k-CNF formula with each clause containing k distinct literals and each clause having a common variable with at most l(k) other clauses, is satisfiable. We establish that the bound on l(k) obtained from the Local Lemma is asymptotically optimal, i.e., . The constructed formulas are all in the class MU(1) of minimal unsatisfiable formulas having one more clause than variables and thus they resolve these asymptotic questions within that class as well. The SAT-formulas are constructed via the binary trees of [10]. In order to construct the trees a continuous setting of the problem is defined, giving rise to a differential equation. The solution of the equation diverges at 0, which in turn implies that the binary tree obtained from the discretization of this solution has the required properties.

The Lovász Local Lemma discovered by Erdős and Lovász in 1975 is a powerful tool to non-constructively prove the existence of combinatorial objects meeting a prescribed collection of criteria. In 1991, József Beck was the first to demonstrate that a constructive variant can be given under certain more restrictive conditions, starting a whole line of research aimed at improving his algorithm's performance and relaxing its restrictions. In the present article, we improve upon recent findings so as to provide a method for making almost all known applications of the general Local Lemma algorithmic.

Including a unique code in each copy of a distributed document is an effective way of fighting intellectual piracy. Codes designed for this purpose that are secure against collusion attacks are called fingerprinting codes. In this paper we consider fingerprinting with the marking assumption and design codes that achieve much higher rates than previous constructions. We conjecture that these codes attain the maximum possible rate (the fingerprinting capacity) for any fixed number of pirates. We prove new upper bounds for the fingerprinting capacity that are not far from the rate of our codes. On the downside the accusation algorithm of our codes are much slower than those of earlier codes. We introduce the novel model of weak fingerprinting codes where one pirate should be caught only if the identity of all other pirates are revealed. We construct fingerprinting codes in this model with improved rates but our upper bound on the rate still applies. In fact, these improved codes achieve the fingerprinting capacity of the weak model by a recent upper bound. Using analytic techniques we compare the rates of our codes in the standard model and the rates of the optimal codes in the weak model. To our surprise these rates asymptotically agree, that is, their ratio tends to 1 as t goes to infinity. Although we cannot prove that each one of our codes in the standard model achieves the fingerprinting capacity, this proves that asymptotically they do.

We construct binary codes for fingerprinting digital documents. Our codes for n users that are ϵ-secure against c pirates have length O ( c 2 log( n /ϵ)). This improves the codes proposed by Boneh and Shaw [1998] whose length is approximately the square of this length. The improvement carries over to works using the Boneh--Shaw code as a primitive, for example, to the dynamic traitor tracing scheme of Tassa [2005]. By proving matching lower bounds we establish that the length of our codes is best within a constant factor for reasonable error probabilities. This lower bound generalizes the bound found independently by Peikert et al. [2003] that applies to a limited class of codes. Our results also imply that randomized fingerprint codes over a binary alphabet are as powerful as over an arbitrary alphabet and the equal strength of two distinct models for fingerprinting.

Given a finite set of complex numbers A we say that a transformation on the complex numbers, T: C → C is k-rich on A if |A ∩ T(A)|≥ k. In this paper we give a bounds on the number of k-rich linear and Mobius transformations for any given set A. Our results have applications to discrete geometry and to additive combinatorics.

Let G be a graph without loops or multiple edges drawn in the plane. It is shown that, for any k, if G has at least $C_k n$ edges and n vertices, then it contains three sets of k edges, such that every edge in any of the sets crosses all edges in the other two sets. Furthermore, two of the three sets can be chosen such that all k edges in the set have a common vertex.

At most how many edges (hyperedges, nonzero entries, characters) can a graph (hypergraph, zero-one matrix, string) have if it does not contain a fixed forbidden pattern? Turán-type extremal graph theory, Erdős--Ko--Rado-type extremal set theory, Ramsey theory, the theory of Davenport--Schinzel sequences, etc. have been developed to address questions of this kind. They produced a number of results that found important applications in discrete and computational geometry.In the present paper, we discuss an extension of extremal graph theory to ordered graphs, i.e., to graphs whose vertex set is linearly ordered. In the most interesting cases, the forbidden ordered graphs are bipartite, and the basic problem can be reformulated as an extremal problem for zero-one matrices avoiding a certain submatrix P. We disprove a general conjecture of Füredi and Hajnal related to the latter problem, and replace it by some weaker alternatives. We verify our conjectures in a few special cases when P is the adjacency matrix of an acyclic graph and discuss the same question when the forbidden patterns are adjacency matrices of cycles.Our results lead to a new proof of the celebrated theorem of Spencer, Szemerédi, and Trotter [15] stating that the number of times that the unit distance can occur among n points in the plane is O(n4/3). This is the first proof that does not use any tool other than a forbidden pattern argument. We present another geometric application, where the forbidden pattern P is the adjacency matrix of an acyclic graph. A hippodrome is a c x d rectangle with two semidisks of diameter d attached to its sides of length d. Improving a result of Efrat and Sharir [5] we show that the number of "free" placements of a convex n-gon in general position in a hippodrome H such that simultaneously three vertices of the polygon lie on the boundary of H, is O(n). This result is related to the Planar Segment-Center Problem.

Twenty years ago, Ajtai, Chvatal, Newborn, Szemeredi, and, independently, Leighton discovered that the crossing number of any graph with v vertices and e>4v edgesis at least ce3/v2, where c>0 is an absolute constant. This result, known as the 'Crossing Lemma,' has found many important applications in discrete and computational geometry. It is tightup to a multiplicative constant. Here we improve the best known value of the constant by showing that the result holds with c>1024/31827>0.032. The proof has two new ingredients, interesting on their own right. We show that (1) if a graph can be drawn in the plane so that every edge crosses at most 3 others, then its number of edges cannot exceed 5.5(v-2); and (2) the crossing number of any graph is at least 73e - 253(v-2). Both bounds are tight up to anadditive constant (the latter one in the range 4v ≤ e ≤ 5v).

Improving an old result of Clarkson et al., we show that the number of distinct distances determined by a set P of n points in three-dimensional space is Ω(n77/141-ε)=Ω(n0.546), for any ε>0. Moreover, there always exists a point p ∈ P from which there are at least these many distinct distances to the remaining elements of P. The same result holds for points on the three-dimensional sphere. As a consequence, we obtain analogous results in higher dimensions.

We construct binary codes for fingerprinting. Our codes for n users that are ε-secure against c pirates have length O(c2 log(n/ε)). This improves the codes proposed by Boneh and Shaw [3] whose length is approximately the square of this length. Our codes are probabilistic. By proving matching lower bounds we establish that the length of these codes is best within a constant factor for reasonable error probabilities. This lower bound generalizes the bound found independently by Peikert, Shelat, and Smith [10] that applies to a limited class of codes. Our results also imply that randomized fingerprint codes over a binary alphabet are as powerful as over an arbitrary alphabet, and also the equal strength of two distinct models for fingerprinting.

A triangle is said to be {\it $\delta$-fat\/} if its smallest angle is at least $\delta>0$. A connected component of the complement of the union of a family of triangles is called a {\it hole}. It is shown that any family of n $\delta$-fat triangles in the plane determines at most $O\left(\frac{n}{\delta}\log\frac{2}{\delta}\right)$ holes. This improves on some earlier bounds of Efrat, Rote, Sharir, and Matousek, et al. Solving a problem of Agarwal and Bern, we also give a general upper bound for the number of holes determined by n triangles in the plane with given angles. As a corollary, we obtain improved upper bounds for the boundary complexity of the union of fat polygons in the plane, which, in turn, leads to better upper bounds for the running times of some known algorithms for motion planning, for finding a separator line for a set of segments, etc.

Article Cutting glass Share on Authors: János Pach Courant Institute, NYU and Rényi Institute, Hungarian Academy Courant Institute, NYU and Rényi Institute, Hungarian AcademyView Profile , Gábor Tardos Rényi Institute, Hungarian Academy Rényi Institute, Hungarian AcademyView Profile Authors Info & Claims SCG '00: Proceedings of the sixteenth annual symposium on Computational geometryMay 2000 Pages 360–369https://doi.org/10.1145/336154.336223Online:01 May 2000Publication History 1citation359DownloadsMetricsTotal Citations1Total Downloads359Last 12 Months11Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We prove that the maximum number of k-sets in a set S of n points in IR 3 is O(nk3/2).This improves substantially the previous best known upper bound of O(nk 5/3) (see [7] and [1]). IntroductionLet S be a set of n points in ]R d, A k-set of S is a subset S' c S such that S' = S N H for some halfspace H and IS'] --k.The problem of determining tight asymptotic bounds on the maximum number of k-sets is one of the most intriguing open problems in combinatorial geometry.Due to its importance in analyzing geometric algorithms [5,9], the problem has caught the attention of computational geometers as well [3,7,8,14,16].A close to optimal solution for the problem remains elusive even in the plane.The best asymptotic upper and lower bounds in the plane are O(nkU3) (see [6]) and n. 2 n(v/iS--~) (see [15]), respectively.In this

A triangle is said to be /spl delta/-fat if its smallest angle is at least /spl delta/>0. A connected component of the complement of the union of a family of triangles is called hole. It is shown that any family of /spl delta/-far triangles in the plane determines at most O (n//spl delta/ log 2//spl delta/) holes. This improves on some earlier bounds of (Efrat et al., 1993; Matousek et al., 1994). Solving a problem of (Agarwal and Bern, 1999) we also give a general upper bound for the number of holes determined by n triangles in the plane with given angles. As a corollary, we obtain improved upper bounds for the boundary complexity of the union of fat polygons in the plane, which, in turn, leads to better upper bounds for the running times of some known algorithms for motion planning, for finding a separator line for a set of segments, etc.

Modular gates are known to be immune for the random restriction techniques of Ajtai (1983), Furst, Saxe, and Sipser (1984), Yao (1985), and Hå stad (1986). We demonstrate here a random clustering technique which overcomes this difficulty and is capable of proving generalizations of several known modular circuit lower bounds of Barrington, Straubing, and Th{érien (1990), Krause and Pudl{ák (1994), and others, characterizing symmetric functions computable by small (MOD p , AND t , MOD m ) circuits. Applying a degree-decreasing technique together with random restriction methods for the AND gates at the bottom level, we also prove a hard special case of the constant degree hypothesis of Barrington, Straubing, and Th{érien (1990) and other related lower bounds for certain (MOD p , MOD m , AND) circuits. Most of the previous lower bounds on circuits with modular gates used special definitions of the modular gates (i.e., the gate outputs one if the sum of its inputs is divisible by m or is not divisible by m) and were not valid for more general MOD m gates. Our methods are applicable, and our lower bounds are valid for the most general modular gates as well.

Consider the set ℋ of all linear (or affine) transformations between two vector spaces over a finite field F . We study how good ℋ is as a class of hash functions, namely we consider hashing a set S of size n into a range having the same cardinality n by a randomly chosen function from ℋ and look at the expected size of the largest hash bucket. ℋ is a universal class of hash functions for any finite field, but with respect to our measure different fields behave differently. If the finite field F has n elements, then there is a bad set S ⊂ F 2 of size n with expected maximal bucket size Ω( n 1/3 ). If n is a perfect square, then there is even a bad set with largest bucket size always at least √n. (This is worst possible, since with respect to a universal class of hash functions every set of size n has expected largest bucket size below √ + 1/2.) If, however, we consider the field of two elements, then we get much better bounds. The best previously known upper bound on the expected size of the largest bucket for this class was O (2 √ log n ). We reduce this upper bound to O (log n log log n ). Note that this is not far from the guarantee for a random function. There, the average largest bucket would be Θ (log n / log log n ). In the course of our proof we develop a tool which may be of independent interest. Suppose we have a subset S of a vector space D over Z 2 , and consider a random linear mapping of D to a smaller vector space R . If the cardinality of S is larger than c ε | R |log| R |, then with probability 1 - ϵ, the image of S will cover all elements in the range.

Modular gates are known to be immune for the random restriction techniques of previous authors. We demonstrate here a random clustering technique which overcomes this difficulty and is capable to prove generalizations of several known modular circuit lower bounds, characterizing symmetric functions computable by small (MOD/sub p/, AND/sub t/, MOD/sub m/) circuits. Applying a degree-decreasing technique together with random restriction methods for the AND gates at the bottom level, we also prove a hard special case of the constant degree hypothesis and other related lower bounds for certain (MOD/sub p/, MOD/sub m/, AND) circuits. Most of the previous lower bounds on circuits with modular gates used special definitions of the modular gates (i.e., the gate outputs one if the sum of its inputs is divisible by m, or is not divisible by m), and were not valid for more general MOD/sub m/ gates. Our methods are applicable-and our lower bounds are valid-for the most general modular gates as well.

Consider the following communication problem. Alice gets a word x/spl isin/{0,1}/sup n/ and Bob gets a word y/spl isin/{0,1}/sup n/. Alice and Bob are told that x/spl ne/y. Their goal is to find an index 1/spl les/i/spl les/n such that x/sub i//spl ne/y/sub i/ (the index i should be known to both of them). This problem is one of the most basic communication problems. It arises naturally from the correspondence between circuit depth and communication complexity discovered by M. Karchmer and A. Wigderson (1990). We present three protocols using which Alice and Bob can solve the problem by exchanging at most it n+2 bits. One of this protocols is due to S. Rudich and G. Tardos. These protocols improve the previous upper bound of n+log* n, obtained by M. Karchmer. We also show that any protocol for solving the problem must exchange, in the worst case, at least n+1 bits. This improves a simple lower bound of n-1 obtained by Karchmer. Our protocols, therefore, are at most one bit away from optimality.

We construct PCPS with strong zero-knowledge properties.First, we construct polynomially bounded (in size) PCP'S for NP which can be checked using poly-Iogarithmic queries, with polynomially low error, yet are statistical zero-knowledge against an adversary that makes U arbitrary queries, where U can be set to any polynomial.Second, we construct PCPS for NEXPTIME that can be checked using polynomially many queries, yet are statistically zero-knowledge against any polynomial y bounded adversary.These PCPS are exponential in size and have exponentially low error.Previously, it was only known how to construct zero-knowledge PCPS with a constant error probability.In the course of constructing these PCP'S we abstract a tool we call locking systems.We provide the definition and also a locking system with very efficient parameters.This mechanism may be useful in other settings as well.

The authors show that if a language has an interactive proof of logarithmic statistical knowledge-complexity, then it belongs to the class /spl Ascr//spl Mscr//spl cap/co-/spl Ascr//spl Mscr/. Thus, if the polynomial time hierarchy does not collapse, then /spl Nscr//spl Pscr/-complete languages do not have logarithmic knowledge complexity. Prior to this work, there was no indication that would contradict /spl Nscr//spl Pscr/ languages being proven with even one bit of knowledge. Next, they consider the relation between the error probability and the knowledge complexity of an interactive proof. They show that if the error probability /spl epsiv/(n) is less than 2/sup -3k(n)/ (where k(n) is the knowledge complexity) then the language proven has to be in the third level of the polynomial time hierarchy. In order to prove their main result, they develop an /spl Ascr//spl Mscr/ protocol for checking that a samplable distribution has a given entropy. They believe that this protocol is of independent interest.

No abstract available.

Planning is defined as the problem of synthesizing a desired behavior from given basic operations, and learning is defined as the dual problem of analyzing a given behavior to determine the unknown basic operations. Algorithms for solving these problems in the context of invertible operations on finite-state environments are developed. In addition to their obvious artificial intelligence applications, the algorithms can efficiently find the shortest way to solve Rubik's cube, test ping-pong protocols, and solve systems of equations over permutation groups.>

The following propositions are considered: (1) E=NE (i.e. it is decidable in exponential time whether there is a solution for an exponential-type search problem). (2) Every exponential-type search problem is solvable in exponential time. (3) The first solution to every exponential-type search problem can be found in exponential time. (4) E=E/sup NP/. It is easy to see that (4) implies (3) implies (2) implies (1). It has been conjectured that the first and last of these assumptions are equivalent in every relativized world. It is proved here that there exist relativized words in which the last two implications are not reversible. This is evidence that the search problem is not reducible to decision problems in exponential time. It is also proved that the third and fourth assumptions are equivalent. The combinatorial core of the separation results is a lower bound on the parallel complexity of a generalized version of the X-search problem.>

Björner, Lvász, and Shor have introduced a chip firing game on graphs. This paper proves a polynomial bound on the length of the game in terms of the number of vertices of the graph provided the length is finite. The obtained bound is best possible within a constant factor.