Gábor Tardos

According to our database1, Gábor Tardos authored at least 100 papers between 1988 and 2019.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
On the Turán number of ordered forests.
J. Comb. Theory, Ser. A, 2019

Planar point sets determine many pairwise crossing segments.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

2018
Tilings with noncongruent triangles.
Eur. J. Comb., 2018

2017
On the Turán number of ordered forests.
Electronic Notes in Discrete Mathematics, 2017

Regular families of forests, antichains and duality pairs of relational structures.
Combinatorica, 2017

On Max-Clique for intersection graphs of sets and the Hadwiger-Debrunner numbers.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Disjointness Graphs of Segments.
Proceedings of the 33rd International Symposium on Computational Geometry, 2017

2016
Improved bounds for the randomized decision tree Complexity of recursive majority.
Random Struct. Algorithms, 2016

Separation with restricted families of sets.
J. Comb. Theory, Ser. A, 2016

The Local Lemma Is Asymptotically Tight for SAT.
J. ACM, 2016

Beyond the Richter-Thomassen Conjecture.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2015
Relations between the Local Chromatic Number and Its Directed Version.
Journal of Graph Theory, 2015

Erdős-Pyber Theorem for Hypergraphs and Secret Sharing.
Graphs and Combinatorics, 2015

On the Richter-Thomassen Conjecture about Pairwise Intersecting Closed Curves.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014
On List Coloring and List Homomorphism of Permutation and Interval Graphs.
SIAM J. Discrete Math., 2014

Conflict-Free Colouring of Graphs.
Combinatorics, Probability & Computing, 2014

2013
Optimal Information Rate of Secret Sharing Schemes on Trees.
IEEE Trans. Information Theory, 2013

Caterpillar Dualities and Regular Languages.
SIAM J. Discrete Math., 2013

On Infinite-finite Duality Pairs of Directed Graphs.
Order, 2013

The Range of a Random Walk on a Comb.
Electr. J. Comb., 2013

Local chromatic number of quadrangulations of surfaces.
Combinatorica, 2013

Cross-Intersecting Families of Vectors.
Proceedings of the Discrete and Computational Geometry and Graphs, 2013

On the Communication Complexity of Sparse Set Disjointness and Exists-Equal Problems.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012
Piercing quasi-rectangles - On a problem of Danzer and Rogers.
J. Comb. Theory, Ser. A, 2012

On-line secret sharing.
Des. Codes Cryptogr., 2012

Remarks on a Ramsey theory for trees.
Combinatorica, 2012

The Visible Perimeter of an Arrangement of Disks.
Proceedings of the Graph Drawing - 20th International Symposium, 2012

2011
On directed local chromatic number, shift graphs, and Borsuk-like graphs.
Journal of Graph Theory, 2011

On-line secret sharing.
IACR Cryptology ePrint Archive, 2011

Piercing Quasi-Rectangles: On a Problem of Danzer and Rogers.
Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

The Local Lemma is Tight for SAT.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Tight bounds for Lp samplers, finding duplicates in streams, and related problems.
Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2011

Tight lower bounds for the size of epsilon-nets.
Proceedings of the 27th ACM Symposium on Computational Geometry, 2011

2010
Crossing numbers of imbalanced graphs.
Journal of Graph Theory, 2010

A constructive proof of the general lovász local lemma.
J. ACM, 2010

Capacity of Collusion Secure Fingerprinting - A Tradeoff between Rate and Efficiency - (Extended Abstract of Invited Talk).
Proceedings of the Information Hiding - 12th International Conference, 2010

2009
Secret sharing on trees: problem solved.
IACR Cryptology ePrint Archive, 2009

Conflict-Free Colourings of Graphs and Hypergraphs.
Combinatorics, Probability & Computing, 2009

High rate fingerprinting codes and the fingerprinting capacity.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2008
Graph Colouring with No Large Monochromatic Components.
Combinatorics, Probability & Computing, 2008

Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

2007
On the maximum number of edges in quasi-planar graphs.
J. Comb. Theory, Ser. A, 2007

Graph coloring with no large monochromatic components.
Electronic Notes in Discrete Mathematics, 2007

Colorful subgraphs in Kneser-like graphs.
Eur. J. Comb., 2007

Deterministic random walks on the integers.
Eur. J. Comb., 2007

Partitioning multi-dimensional sets in a small number of "uniform" parts.
Eur. J. Comb., 2007

Multiple Coverings of the Plane with Triangles.
Discrete & Computational Geometry, 2007

Coloring Axis-Parallel Rectangles.
Proceedings of the Computational Geometry and Graph Theory, 2007

On the number of k-rich transformations.
Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, 2007

2006
Improving the Crossing Lemma by Finding More Crossings in Sparse Graphs.
Discrete & Computational Geometry, 2006

Waiting for a Bat to Fly By (in Polynomial Time).
Combinatorics, Probability & Computing, 2006

Extremal Problems For Transversals In Graphs With Bounded Degree.
Combinatorica, 2006

Local Chromatic Number, KY Fan's Theorem, And Circular Colorings.
Combinatorica, 2006

Deterministic Random Walks.
Proceedings of the Third Workshop on Analytic Algorithmics and Combinatorics, 2006

2005
On 0-1 matrices and small excluded submatrices.
J. Comb. Theory, Ser. A, 2005

Partitioning multi-dimensional sets in a small number of "uniform" parts
Electronic Colloquium on Computational Complexity (ECCC), 2005

Forbidden patterns and unit distances.
Proceedings of the 21st ACM Symposium on Computational Geometry, 2005

Indecomposable Coverings.
Proceedings of the Discrete Geometry, 2005

2004
Excluded permutation matrices and the Stanley-Wilf conjecture.
J. Comb. Theory, Ser. A, 2004

Crossing Stars in Topological Graphs.
Proceedings of the Discrete and Computational Geometry, Japanese Conference, 2004

Intersection Reverse Sequences and Geometric Applications.
Proceedings of the Graph Drawing, 12th International Symposium, 2004

Improving the crossing lemma by finding more crossings in sparse graphs: [extended abstract].
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

2003
A Note on Non-Deterministic Communication Complexity with Few Witnesses.
Theory Comput. Syst., 2003

Bounded size components--partitions and transversals.
J. Comb. Theory, Ser. B, 2003

Optimal probabilistic fingerprint codes.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Distinct distances in three and higher dimensions.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

2002
Covering lattice points by subspaces.
Periodica Mathematica Hungarica, 2002

Isosceles Triangles Determined by a Planar Point Set.
Graphs and Combinatorics, 2002

The k Most Frequent Distances in the Plane.
Discrete & Computational Geometry, 2002

On the Knowledge Complexity of NP.
Combinatorica, 2002

Geometric Graphs with No Self-intersecting Path of Length Three.
Proceedings of the Graph Drawing, 10th International Symposium, 2002

2001
Separating convex sets by straight lines.
Discrete Mathematics, 2001

A Multidimensional Generalization Of The Erdös-Szekeres Lemma On Monotone Subsequences.
Combinatorics, Probability & Computing, 2001

Untangling a Polygon.
Proceedings of the Graph Drawing, 9th International Symposium, 2001

2000
Lower Bounds for (MODp-MODm) Circuits.
SIAM J. Comput., 2000

Ups and Downs of First Order Sentences on Random Graphs.
Combinatorica, 2000

On the boundary complexity of the union of fat triangles.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

An Improved Bound for k-Sets in Three Dimensions.
EuroCG, 2000

An improved bound for k-sets in three dimensions.
Proceedings of the Sixteenth Annual Symposium on Computational Geometry, 2000

Cutting glass.
Proceedings of the Sixteenth Annual Symposium on Computational Geometry, 2000

1999
Linear Hash Functions.
J. ACM, 1999

1998
Lower Bounds for (MOD p -- MOD m) Circuits
Electronic Colloquium on Computational Complexity (ECCC), 1998

Lower Bounds for (MOD p - MOD m) Circuits.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Arthur-Merlin Games in Boolean Decision Trees.
Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

1997
Arthur-Merlin Games in Boolean Decision Trees
Electronic Colloquium on Computational Complexity (ECCC), 1997

Probabilistically Checkable Proofs with Zero Knowledge.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Is Linear Hashing Good?
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

The Communication Complexity of the Universal Relation.
Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

1996
On Point Covers of Multiple Intervals and Axis-Parallel Rectangles.
Combinatorica, 1996

On the Knowledge Complexity of NP.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995
Transversals of 2-Intervals, a Topological Approach.
Combinatorica, 1995

A Lower Bound on the Mod 6 Degree of the OR Function.
Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995

1994
On the Power of Randomization in On-Line Algorithms.
Algorithmica, 1994

Multi-Prover Encoding Schemes and Three-Prover Proof Systems.
Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

1990
On the Power of Randomization in Online Algorithms (Extended Abstract)
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

A Competitive 3-Server Algorithm.
Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990

1989
Query complexity, or why is it difficult to seperate NP A cap co NPA from PA by random oracles A?.
Combinatorica, 1989

Decision Versus Search Problems in Super-Polynomial Time
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

Planning and Learning in Permutation Groups
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

1988
Polynomial Bound for a Chip Firing Game on Graphs.
SIAM J. Discrete Math., 1988


  Loading...