# Endre Szemerédi

#1,034

Most Influential Person Now

Hungarian-American mathematician and theoretical computer scientist

## Endre Szemerédi's AcademicInfluence.com Rankings

Endre Szemerédimathematics Degrees

Mathematics

#72

World Rank

#209

Historical Rank

Combinatorics

#5

World Rank

#6

Historical Rank

Graph Theory

#12

World Rank

#17

Historical Rank

Number Theory

#28

World Rank

#47

Historical Rank

Endre Szemerédicomputer-science Degrees

Computer Science

#238

World Rank

#248

Historical Rank

Theoretical Computer Science

#6

World Rank

#6

Historical Rank

## Download Badge

Mathematics Computer Science

## Endre Szemerédi's Degrees

- PhD Mathematics Moscow State University

## Why Is Endre Szemerédi Influential?

(Suggest an Edit or Addition)According to Wikipedia, Endre Szemerédi is a Hungarian-American mathematician and computer scientist, working in the field of combinatorics and theoretical computer science. He has been the State of New Jersey Professor of computer science at Rutgers University since 1986. He also holds a professor emeritus status at the Alfréd Rényi Institute of Mathematics of the Hungarian Academy of Sciences.

## Endre Szemerédi's Published Works

### Published Works

- On sets of integers containing k elements in arithmetic progression (1975) (1176)
- Regular Partitions of Graphs (1975) (1126)
- Storing a sparse table with O(1) worst case access time (1982) (937)
- An 0(n log n) sorting network (1983) (598)
- Extremal problems in discrete geometry (1983) (581)
- Many hard examples for resolution (1988) (519)
- O(n LOG n) SORTING NETWORK. (1983) (467)
- A Note on Ramsey Numbers (1980) (365)
- Sorting inc logn parallel steps (1983) (361)
- Crossing-Free Subgraphs (1982) (336)
- Blow-up Lemma (1997) (311)
- Deterministic simulation in LOGSPACE (1987) (237)
- On the Complexity of Matrix Group Problems I (1984) (230)
- A Dirac-Type Theorem for 3-Uniform Hypergraphs (2006) (228)
- Sorting in c log n parallel sets (1983) (226)
- On the probability that a random ±1-matrix is singular (1995) (218)
- Theory of algorithms (1985) (211)
- Limit distribution for the existence of Hamiltonian cycles in a random graph (2006) (198)
- Unit distances in the Euclidean plane (1984) (195)
- The Ramsey number of a graph with bounded maximum degree (1983) (180)
- The Regularity Lemma and Its Applications in Graph Theory (2000) (168)
- A Dense Infinite Sidon Sequence (1981) (154)
- A statistical theorem of set addition (1994) (152)
- Proof of the Alon-Yuster conjecture (2001) (144)
- An approximate Dirac-type theorem for k-uniform hypergraphs (2008) (142)
- Proof of the Seymour conjecture for large graphs (1998) (140)
- Perfect matchings in large uniform hypergraphs with large minimum collective degree (2009) (140)
- On the second eigenvalue of random regular graphs (1989) (140)
- An Optimal-Time Algorithm for Slope Selection (1989) (132)
- Largest random component of ak-cube (1982) (127)
- On determinism versus non-determinism and related problems (1983) (122)
- A Lower Bound for Heilbronn'S Problem (1982) (118)
- On sums and products of integers (1983) (117)
- The longest path in a random graph (1981) (116)
- An algorithmic version of the blow-up lemma (1996) (97)
- Topological cliques in graphs II (1994) (97)
- On the square of a Hamiltonian cycle in dense graphs (1996) (95)
- A Cure for the Telephone Disease (1972) (95)
- Three-Color Ramsey Numbers For Paths (2007) (93)
- On sparse graphs with dense long paths. (1975) (90)
- Extremal Uncrowded Hypergraphs (1982) (90)
- An improved bound for the monochromatic cycle partition number (2006) (87)
- Induced subtrees in graphs of large chromatic number (1980) (81)
- Two lower bounds for branching programs (1986) (77)
- Topological Cliques in Graphs (1994) (77)
- On the Pósa-Seymour conjecture (1998) (77)
- Partitioning Two-Coloured Complete Graphs into Two Monochromatic Cycles (1998) (77)
- More results on Ramsey—Turán type problems (1983) (75)
- An upper bound on the number of planar k-sets (1989) (72)
- Perfect matchings in uniform hypergraphs with large minimum degree (2006) (72)
- A fast algorithm for equitable coloring (2010) (70)
- Dirac-type conditions for hamiltonian paths and cycles in 3-uniform hypergraphs (2011) (69)
- On sets of natural numbers whose difference set contains no squares (1988) (69)
- On sets of integers containing no four elements in arithmetic progression (1969) (67)
- The Analysis of Double Hashing (1978) (64)
- On Turán’s theorem for sparse graphs (1981) (64)
- Proof of a Packing Conjecture of Bollobás (1995) (64)
- On a problem of Davenport and Schinzel (1974) (62)
- Undirected Connectivity in O(log ^1.5 n) Space (1992) (62)
- The number of different distances determined by a set of points in the Euclidean plane (1992) (62)
- On Size Ramsey Numbers of Graphs with Bounded Degree (2000) (61)
- Undirected connectivity in O(log/sup 1.5/n) space (1992) (60)
- How to avoid using the Regularity Lemma: Pósa's conjecture revisited (2010) (60)
- Extremal Graphs without Large Forbidden Subgraphs (1978) (53)
- On a question of Erdős and Moser (2005) (52)
- Combinatorial Properties of Systems of Sets (1978) (51)
- Undirected Connectivity in O(l~gl*~ n) Space* (1992) (50)
- Sparse partition universal graphs for graphs of bounded degree (2011) (50)
- On complete subgraphs of r-chromatic graphs (1975) (48)
- Difference sets without κ-th powers (1994) (47)
- Partitioning 3-Colored Complete Graphs into Three Monochromatic Cycles (2011) (46)
- Universality and tolerance (2000) (46)
- Linear problems in combinatorial number theory (1975) (46)
- Three-color Ramsey numbers for paths (2008) (45)
- Finite and infinite arithmetic progressions in sumsets (2006) (44)
- Integer sets containing no arithmetic progressions (1990) (43)
- Dense Graphs without 3-Regular Subgraphs (1995) (42)
- On a conjecture of Erdös and Heilbronn (1970) (42)
- Matching nuts and bolts in O(n log n) time (1996) (41)
- Lower Bounds to the Complexity of Symmetric Boolean Functions (1990) (40)
- On Heilbronn's Triangle Problem (1981) (40)
- Long arithmetic progressions in sumsets: Thresholds and bounds (2005) (37)
- Construction of a thin set with small fourier coefficients (1990) (37)
- On the ErdÖS-Stone Theorem (1981) (36)
- On nontrivial separators for k-page graphs and simulations by nondeterministic one-tape Turing machines (1986) (36)
- Tripartite Ramsey numbers for paths (2007) (36)
- Proof of a Conjecture of Bollobás and Eldridge for Graphs of Maximum Degree Three* (2003) (35)
- On a problem of graph theory (1967) (35)
- Quadripartite version of the Hajnal-Szemerédi theorem (2008) (35)
- A Combinatorial Distinction Between the Euclidean and Projective Planes (1983) (34)
- Girth of sparse graphs (2002) (34)
- Constructing Small Sets that are Uniform in Arithmetic Progressions (1993) (33)
- On the distribution of cycle lengths in graphs (1984) (33)
- Fault tolerant graphs, perfect hash functions and disjoint paths (1992) (33)
- The Ramsey Number of Diamond-Matchings and Loose Cycles in Hypergraphs (2008) (32)
- An upper bound on the number of planarK-sets (1992) (32)
- Deterministic selection in O(loglog N) parallel time (1986) (30)
- The Approximate Loebl-Komlós-Sós Conjecture IV: Embedding Techniques and the Proof of the Main Result (2014) (30)
- Near-optimum Universal Graphs for Graphs with Bounded Degrees (2001) (29)
- Optimal Parallel Selection has Complexity O(Log Log n) (1989) (28)
- The Approximate Loebl-Komlós-Sós Conjecture III: The Finer Structure of LKS Graphs (2014) (28)
- The Approximate Loebl-Komlós-Sós Conjecture II: The Rough Structure of LKS Graphs (2014) (27)
- Spanning Trees in Dense Graphs (2001) (27)
- A note on perfect matchings in uniform hypergraphs with large minimum collective degree (2008) (27)
- On the number of Hamiltonian cycles in Dirac graphs (2003) (27)
- The Approximate Loebl-Komlós-Sós Conjecture I: The Sparse Decomposition (2014) (27)
- A Lower Bound for Read-Once-Only Branching Programs (1987) (26)
- Turán-Ramsey theorems and simple asymptotically extremal structures (1993) (26)
- Long Arithmetic Progressions in Sum‐Sets and the Number x‐Sum‐Free Sets (2005) (25)
- Subset sums modulo a prime (2008) (25)
- On the Number of Monochromatic Solutions of ${\bm x}+{\bm y}={\bm z}^{{\bm 2}}$ (2006) (24)
- Turán-Ramsey Theorems and Kp-Independence Numbers (1994) (24)
- Two tapes are better than one for off-line Turing machines (1987) (22)
- The Parallel Complexity of Element Distinctness is Omega (sqrt(log n)) (1988) (21)
- Brooks Coloring in Parallel (1990) (20)
- On coloring graphs with locally small chromatic number (1984) (19)
- Almost Sorting in one Round (1989) (19)
- On Almost Bipartite Large Chromatic Graphs (1982) (18)
- THE APPROXIMATE LOEBL-KOMLOS-SOS CONJECTURE AND EMBEDDING TREES IN SPARSE GRAPHS (2014) (17)
- Tight Bounds for Embedding Bounded Degree Trees (2010) (17)
- One-sided Coverings of Colored Complete Bipartite Graphs (2006) (17)
- Halvers and Expanders (1992) (17)
- On the difference of consecutive terms of sequences defined by divisibility properties, II (1973) (16)
- Short cycles in directed graphs (1983) (15)
- Long Monochromatic Berge Cycles in Colored 4-Uniform Hypergraphs (2010) (15)
- Monochromatic Matchings in the Shadow Graph of Almost Complete Hypergraphs (2010) (15)
- Optimal Slope Selection (1988) (14)
- On An Extremal Problem Concerning Primitive Sequences (1967) (14)
- On 3-pushdown graphs with large separators (1989) (14)
- Stability of the path-path Ramsey number (2009) (14)
- Upper bound for transversals of tripartite hypergraphs (1982) (13)
- Infinite sets of primes with fast primality tests and quick generation of large primes (1989) (13)
- A Practical Regularity Partitioning Algorithm and its Applications in Clustering (2012) (13)
- On a theorem of Behrend (1967) (13)
- On the Hamiltonicity of Triple Systems with High Minimum Degree (2016) (12)
- Monochromatic Hamiltonian 3‐tight Berge cycles in 2‐colored 4‐uniform hypergraphs (2010) (11)
- Short paths in quasi-random triple systems with sparse underlying graphs (2006) (10)
- On a problem of Graham (2022) (9)
- On a problem in additive number theory (1994) (9)
- There is no Fast Single Hashing Algorithm (1978) (9)
- Erdős's Unit Distance Problem (2016) (9)
- Lower bounds for sorting networks (1995) (9)
- The analysis of double hashing(Extended Abstract) (1976) (8)
- Halvers and expanders (switching) (1992) (8)
- On some extremal properties of sequences of integers. II. (2022) (8)
- Notes on the erdös-stone theorem (1983) (7)
- Two infinite sets of primes with fast primality tests (1988) (7)
- Spanning subgraphs of dense graphs and a combinatorial problem on strings (1998) (7)
- Is laziness paying off? ("Absorbing" method) (2013) (6)
- Monochromatic Hamiltonian 3-tight Berge cycles in 2-colored 4-uniform hypergraphs (2010) (6)
- Two tapes versus one for off-line Turing machines (1993) (5)
- On the solvability of the equations [ai, aj] = ar and (a′i, a′j) = a′r in sequences of positive density (1966) (5)
- Some additive and multiplicative problem sin number theory (1975) (5)
- Embedding spanning subgraphs into large dense graphs (2010) (4)
- Tight bound for the density of sequence of integers the sum of no two of which is a perfect square (2002) (4)
- On the divisibility properties of sequences of integers (II) (1968) (4)
- Arithmetic Progressions, Different Regularity Lemmas and Removal Lemmas (2015) (4)
- An old new proof of Roth’s theorem (2007) (4)
- On subgraph number independence in trees (1978) (3)
- On the sum of the reciprocals of cycle lengths in sparse graphs (1985) (3)
- On a problem of P. Erdos and S. Stein (1968) (3)
- A Tribute to Paul Erdős: Generating expanders from two permutations (1990) (3)
- ON THE NUMBER OF SOLUTIONS OF (1973) (2)
- On coverings of random graphs (1982) (2)
- Structural Approach to Subset Sum Problems (2016) (2)
- On the running time of the Adleman--Pomerance--Rumely primality test (2000) (2)
- Combinatorics, Geometry and Probability: Turán–Ramsey Theorems and Kp -Independence Numbers (1997) (2)
- On the divisibility properties of integers (I) (1966) (2)
- Sorting in Average Time o(log) n (1989) (1)
- There are no p-Complete Families of Symmetric Boolean Functions (1989) (1)
- Two Geometrical Applications of the Semi-random Method (2018) (1)
- On the Solvability of Certain Equations in Sequences of Positive Upper Logarithmic Density (1968) (1)
- On sum-free subsequences (1975) (1)
- Subset sums in $\BZ_p$ (2006) (1)
- Various Regularity Lemmas in Graphs and Hypergraphs (2013) (1)
- Számelmélet és kombinatorikus vonatkozásai = Number Theory and its Interactions with Combinatorics (2008) (0)
- Arithmetic Progressions, Different Regularity Lemmas and Removal Lemmas (2015) (0)
- Finding spanning subgraphs of dense graphs and some new results on the k-server problem (2000) (0)
- Diszkrét matematika = Discrete mathematics (2009) (0)
- The Average-Case Area of Heilbronn-Type Triangles∗ (2013) (0)
- On the Hamiltonicity of Triple Systems with High Minimum Degree (2017) (0)
- On an Extremal Problem Concerning Intervals (1982) (0)
- SUBSET SUMS IN Zp (2006) (0)
- ON THE NUMBER OF SOLUTIONS OF P, ERDijS AND E. SZEMEREDI (2001) (0)
- Packing theorems in graph theory and packing integer programs (2007) (0)
- WPI-CS-TR-12-05 September 2012 A Practical Regularity Partitioning (2013) (0)
- Additive combinatorics and graph theory (2018) (0)
- On-line algorithms and fast digital identity revocation (2002) (0)
- On a problem of P. Erdős (1973) (0)
- Structural Approach to Subset Sum Problems (2016) (0)
- C O ] 4 O ct 2 01 9 On distinct consecutive differences (2019) (0)
- The Generalization of Dirac's Theorem for Hypergraphs (2005) (0)
- Szemerédi ’ s regularity lemma 1 . Szemerédi ’ s regularity lemma (2012) (0)
- The longest path in a random graph [WAIT to hear from author; wrong PDF sent] (2020) (0)

This paper list is powered by the following services:

## Other Resources About Endre Szemerédi

## What Schools Are Affiliated With Endre Szemerédi?

Endre Szemerédi is affiliated with the following schools: