scientific article; zbMATH DE number 1324671

Publication date: 17 August 1999

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

combinatorics Ramsey theory extremal set theory lower bounds probabilistic method span programs linear algebra method

Extremal set theory (05D05) Ramsey theory (05D10) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics (05-01) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items

Sixty years of network reliability ⋮ Kolmogorov width of discrete linear spaces: an approach to matrix rigidity ⋮ The relative exponential time complexity of approximate counting satisfying assignments ⋮ A note on the size of minimal covers ⋮ Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey ⋮ Two algorithms for LCS consecutive suffix alignment ⋮ A Boolean measure of similarity ⋮ Treewidth computation and extremal combinatorics ⋮ On sunflowers and matrix multiplication ⋮ DNF sparsification and a faster deterministic counting algorithm ⋮ Separation and Witnesses ⋮ On minimum saturated matrices ⋮ The covering radius problem for sets of 1-factors of the complete uniform hypergraphs ⋮ On kernelization and approximation for the vector connectivity problem ⋮ Note on maximal bisection above tight lower bound ⋮ On the complexity of deciding avoidability of sets of partial words ⋮ The inverse Shapley value problem ⋮ The Relative Exponential Time Complexity of Approximate Counting Satisfying Assignments ⋮ Parameterized Algorithms and Kernels for 3-Hitting Set with Parity Constraints ⋮ Lattices and hypergraphs associated to square-free monomial ideals ⋮ Singular surfaces, mod 2 homology, and hyperbolic volume. II. ⋮ Unnamed Item ⋮ More on the Magnus-Derek game ⋮ A modular approach to shared-memory consensus, with applications to the probabilistic-write model ⋮ Extremal bipartite independence number and balanced coloring ⋮ The unbounded-error communication complexity of symmetric functions ⋮ Random low-degree polynomials are hard to approximate ⋮ On strategy improvement algorithms for simple stochastic games ⋮ Optimal cover time for a graph-based coupon collector process ⋮ Problems and results in extremal combinatorics. I. ⋮ Toric algebra of hypergraphs ⋮ Forbidden graphs for classes of split-like graphs ⋮ On the automatizability of polynomial calculus ⋮ Dominating set is fixed parameter tractable in claw-free graphs ⋮ Set systems: order types, continuous nondeterministic deformations, and quasi-orders ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ Witness Sets ⋮ On the induced matching problem ⋮ The Parameterized Complexity of the Unique Coverage Problem ⋮ Problems and results in extremal combinatorics. II ⋮ Choosability of graphs with infinite sets of forbidden differences ⋮ Reaction systems and extremal combinatorics properties ⋮ The hardest halfspace ⋮ Enumerating matroids of fixed rank ⋮ Maximum cardinality neighbourly sets in quadrilateral free graphs ⋮ An initial study of time complexity in infinite-domain constraint satisfaction ⋮ Lower bounds for the transition complexity of NFAs ⋮ The multicovering radius problem for some types of discrete structures ⋮ Hypergraph encodings of arbitrary toric ideals ⋮ Optimal bounds for sign-representing the intersection of two halfspaces by polynomials ⋮ Dispersing hash functions ⋮ Partial covering arrays: algorithms and asymptotics ⋮ Invitation to intersection problems for finite sets ⋮ Random deviations of ergodic sums for the Pascal adic transformation in the case of the Lebesgue measure ⋮ Estimating parameters associated with monotone properties ⋮ Balanced Hashing, Color Coding and Approximate Counting ⋮ Mediated digraphs and quantum nonlocality ⋮ \(\{0, 2 \}\)-degree free spanning forests in graphs ⋮ On matrices, automata, and double counting in constraint programming ⋮ Locally consistent constraint satisfaction problems ⋮ Cancellation-free circuits in unbounded and bounded depth ⋮ Unrestricted vs restricted cut in a tableau method for Boolean circuits ⋮ Avoiding arithmetic progressions in cyclic groups