Arrow Research search

Author name cluster

Gábor Tardos

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

21 papers
1 author row

Possible papers

21

SODA Conference 2017 Conference Paper

On Max-Clique for intersection graphs of sets and the Hadwiger-Debrunner numbers

  • Chaya Keller
  • Shakhar Smorodinsky
  • Gábor Tardos

Let HD d ( 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 HD d ( p, q ) exists for all P ≥ q ≥ d +1. Specifically, they prove that HD d ( p, d + 1) is This paper has two parts. In the first part we present several improved bounds on HD d ( p, q ). In particular, we obtain the first near tight estimate of HD d ( 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.

Details

SODA Conference 2016 Conference Paper

Beyond the Richter-Thomassen Conjecture

  • János Pach
  • Natan Rubin
  • Gábor Tardos

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)) n 2.

Details

FOCS Conference 2013 Conference Paper

On the Communication Complexity of Sparse Set Disjointness and Exists-Equal Problems

  • Mert Saglam
  • Gábor Tardos

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] n and the goal is to determine whether there exists a coordinate i such that x i = y i. 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.

Details

SODA Conference 2011 Conference Paper

The Local Lemma is Tight for SAT

  • Heidi Gebauer
  • Tibor Szabó
  • Gábor Tardos

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.

Details

STOC Conference 2003 Conference Paper

Distinct distances in three and higher dimensions

  • Boris Aronov
  • János Pach
  • Micha Sharir
  • Gábor Tardos

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 Ω(n 77/141-ε )=Ω(n 0.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.

Details

STOC Conference 2003 Conference Paper

Optimal probabilistic fingerprint codes

  • Gábor Tardos

We construct binary codes for fingerprinting. 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 [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.

Details

FOCS Conference 2000 Conference Paper

On the boundary complexity of the union of fat triangles

  • János Pach
  • Gábor Tardos

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.

Details

FOCS Conference 1998 Conference Paper

Lower Bounds for (MOD p - MOD m) Circuits

  • Vince Grolmusz
  • Gábor Tardos

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.

Details

FOCS Conference 1996 Conference Paper

On the Knowledge Complexity of NP

  • Erez Petrank
  • Gábor Tardos

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.

Details

FOCS Conference 1989 Conference Paper

Decision Versus Search Problems in Super-Polynomial Time

  • Russell Impagliazzo
  • Gábor Tardos

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. >

Details

FOCS Conference 1989 Conference Paper

Planning and Learning in Permutation Groups

  • Amos Fiat
  • Shahar Moses
  • Adi Shamir
  • Ilan Shimshoni
  • Gábor Tardos

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. >

Details
v2026.09.13