Arrow Research search

Author name cluster

Eric Lehman

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.

7 papers
1 author row

Possible papers

7

STOC Conference 2002 Conference Paper

Approximating the smallest grammar: Kolmogorov complexity in natural models

  • Moses Charikar
  • Eric Lehman
  • Ding Liu
  • Rina Panigrahy
  • Manoj Prabhakaran 0001
  • April Rasala
  • Amit Sahai
  • Abhi Shelat

We consider the problem of finding the smallest context-free grammar that generates exactly one given string of length n . The size of this grammar is of theoretical interest as an efficiently computable variant of Kolmogorov complexity. The problem is of practical importance in areas such as data compression and pattern extraction.The smallest grammar is known to be hard to approximate to within a constant factor, and an o (log n /log log n ) approximation would require progress on a long-standing algebraic problem [10]. Previously, the best proved approximation ratio was O ( n 1/2 ) for the Bisection algorithm [8]. Our main result is an exponential improvement of this ratio; we give an O (log ( n/g * )) approximation algorithm, where g * is the size of the smallest grammar.We then consider other computable variants of Kolomogorov complexity. In particular we give an O (log 2 n ) approximation for the smallest non-deterministic finite automaton with advice that produces a given string. We also apply our techniques to "advice-grammars" and "edit-grammars", two other natural models of string complexity.

Details

STOC Conference 2002 Conference Paper

Monotonicity testing over general poset domains

  • Eldar Fischer
  • Eric Lehman
  • Ilan Newman
  • Sofya Raskhodnikova
  • Ronitt Rubinfeld
  • Alex Samorodnitsky

The field of property testing studies algorithms that distinguish, using a small number of queries, between inputs which satisfy a given property, and those that are 'far' from satisfying the property. Testing properties that are defined in terms of monotonicity has been extensively investigated, primarily in the context of the monotonicity of a sequence of integers, or the monotonicity of a function over the n -dimensional hypercube {1,…, m } n . These works resulted in monotonicity testers whose query complexity is at most polylogarithmic in the size of the domain.We show that in its most general setting, testing that Boolean functions are close to monotone is equivalent, with respect to the number of required queries, to several other testing problems in logic and graph theory. These problems include: testing that a Boolean assignment of variables is close to an assignment that satisfies a specific 2 -CNF formula, testing that a set of vertices is close to one that is a vertex cover of a specific graph, and testing that a set of vertices is close to a clique.We then investigate the query complexity of monotonicity testing of both Boolean and integer functions over general partial orders. We give algorithms and lower bounds for the general problem, as well as for some interesting special cases. In proving a general lower bound, we construct graphs with combinatorial properties that may be of independent interest.

Details

FOCS Conference 1998 Conference Paper

Testing Monotonicity

  • Oded Goldreich 0001
  • Shafi Goldwasser
  • Eric Lehman
  • Dana Ron

We present a (randomized) test for monotonicity of Boolean functions. Namely, given the ability to query an unknown function f: {0, 1}/sup n/-{0, 1} at arguments of its choice, the test always accepts a monotone f, and rejects f with high probability if it is /spl epsiv/-far from being monotone (i. e. , every monotone function differs from f on more than an /spl epsiv/ fraction of the domain). The complexity of the test is poly(n//spl epsiv/). The analysis of our algorithm relates two natural combinatorial quantities that can be measured with respect to a Boolean function; one being global to the function and the other being local to it. We also consider the problem of testing monotonicity based only on random examples labeled by the function. We show an /spl Omega/(/spl radic/2/sup n///spl epsiv/) lower bound on the number of required examples, and provide a matching upper bound (via an algorithm).

Details
v2026.09.13