Arrow Research search

Author name cluster

Ilan Newman

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.

19 papers
2 author rows

Possible papers

19

STOC Conference 2024 Conference Paper

Hardness Condensation by Restriction

  • Mika Göös
  • Ilan Newman
  • Artur Riazanov
  • Dmitry Sokolov 0001

Can every n -bit boolean function with deterministic query complexity k ≪ n be restricted to O ( k ) variables such that the query complexity remains Ω( k )? That is, can query complexity be condensed via restriction? We study such hardness condensation questions in both query and communication complexity, proving two main results. Negative: Query complexity cannot be condensed in general: There is a function f with query complexity k such that any restriction of f to O ( k ) variables has query complexity O ( k 3/4 ). Positive: Randomised communication complexity can be condensed for the sink-of-xor function. This yields a quantitatively improved counterexample to the log-approximate-rank conjecture, achieving parameters conjectured by Chattopadhyay, Garg, and Sherif (2021). Along the way we show the existence of Shearer extractors — a new type of seeded extractor whose output bits satisfy prescribed dependencies across distinct seeds.

Details

SODA Conference 2017 Conference Paper

Testing for Forbidden Order Patterns in an Array

  • Ilan Newman
  • Yuri Rabinovich
  • Deepak Rajendraprasad
  • Christian Sohler

In this paper, we study testing of sequence properties that are defined by forbidden order patterns. A sequence f: {1, …, n} → ℝ of length n contains a pattern is the group of permutations of k elements), iff there are indices i 1 < i 2 < · · · < i k, such that f (i x ) > f (i y ) whenever π(χ) > π( y ). If f does not contain π, we say f is π-free. For example, for π = (2, 1), the property of being π-free is equivalent to being non-decreasing, i. e. monotone. The property of being ( k, k — 1, …, 1)-free is equivalent to the property of having a partition into at most k - 1 non-decreasing subsequences. Let k constant, be a (forbidde n ) pattern. Assuming f is stored in an array, we consider the property testing problem of distinguishing the case that f is π-free from the case that f differs in more than en places from any π-free sequence. We show the following results: There is a clear dichotomy between the monotone patterns and the non-monotone ones: For monotone patterns of length k, i. e. , ( k, k - 1, …, 1) and (1, 2, …, k ), we design non-adaptive one-sided error ε-tests of (∊ −1 log n ) O ( k 2 ) query complexity. For non-monotone patterns, we show that for any size- k non-monotone π, any non-adaptive one-sided error ε-test requires at least Ω(γ / η) queries. This general lower bound can be further strengthened for specific non-monotone k -length patterns to Ω( n 1–2/( k +1) ). On the other hand, there always exists a non- adaptive one-sided error ε-test for with O(e −1/k n 1–1/k ) query complexity Again, this general upper bound can be further strengthened for specific non-monotone patterns. E. g. , for π = (1, 3, 2), we describe an ε-test with (almost tight) query complexity of Finally, we show that adaptivity can make a big difference in testing non-monotone patterns, and develop an adaptive algorithm that for any tests π-freeness by making (∊ −1 logn) O(1) queries. For all algorithms presented here, the running times are linear in their query complexity.

Details

STOC Conference 2011 Conference Paper

Every property of hyperfinite graphs is testable

  • Ilan Newman
  • Christian Sohler

A property testing algorithm for a property Π in the bounded degree graph model[7] is an algorithm that, given access to the adjacency list representation of a graph G=(V,E) with maximum degree at most d, accepts G with probability at least 2/3 if G has property Π, and rejects G with probability at least 2/3, if it differs on more than ε dn edges from every d-degree bounded graph with property Π. A property is testable , if for every ε,d and n, there is a property testing algorithm A ε,n,d that makes at most q(ε,d) queries to an input graph of n vertices, that is, a non-uniform algorithm that makes a number of queries that is independent of the graph size.

Details

STOC Conference 2006 Conference Paper

A combinatorial characterization of the testable graph properties: it's all about regularity

  • Noga Alon
  • Eldar Fischer
  • Ilan Newman
  • Asaf Shapira

A common thread in recent results concerning the testing of dense graphs is the use of Szemerédi's regularity lemma. In this paper we show that in some sense this is not a coincidence. Our first result is that the property defined by having any given Szemerédi-partition is testable with a constant number of queries. Our second and main result is a purely combinatorial characterization of the graph properties that are testable with a constant number of queries. This characterization (roughly) says that a graph property P can be tested with a constant number of queries if and only if testing P can be reduced to testing the property of satisfying one of finitely many Szemerédi-partitions. This means that in some sense, testing for Szemerédi-partitions is as hard as testing any testable graph property. We thus resolve one of the main open problems in the area of property-testing, which was raised in the 1996 paper of Goldreich, Goldwasser and Ron [25] that initiated the study of graph property-testing. This characterization also gives an intuitive explanation as to what makes a graph property testable.

Details

STOC Conference 2005 Conference Paper

Testing versus estimation of graph properties

  • Eldar Fischer
  • Ilan Newman

The topic of tolerant property testing, that of distinguishing input instances that are far from satisfying a property from those that are close enough to satisfying it (as opposed to distinguishing the far instances only from the satisfying instances), has recently become an active topic of research in the field of combinatorial property testing [13]. In the general setting, there exist properties that are testable but not tolerantly testable [10]. However, we show here that in the setting of the dense graph model, all testable properties are not only tolerantly testable, but also admit a constant query size algorithm that estimates the distance from the property up to any fixed additive constant.In the course of the construction of this algorithm we develop a framework for extending Szemerédi's Regularity Lemma, both as a prerequisite for formulating what kind of information about the input graph will provide us with the correct estimation, and as the means for efficiently gathering this information. This work is also connected to the question of finding a combinatorial characterization of the testable graph properties, and to the question of efficiently finding a regular partition.

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

STOC Conference 2001 Conference Paper

Testing of matrix properties

  • Eldar Fischer
  • Ilan Newman

Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property P and an input f , distinguish between the case that f satisfies P , and the case that no input that differs from f in less than some fixed fraction of the places satisfies P . An (ε,q) -test for P is a randomized algorithm that queries at most q places of an input x and distinguishes with probability 2/3 between the case that f has the property and the case that at least an ε -fraction of the places of f need to be changed in order for it to have the property.

Details

FOCS Conference 2000 Conference Paper

Testing of Functions that have small width Branching Programs

  • Ilan Newman

Combinatorial property testing, initiated formally by (Goldreich et al. , 1996) and inspired by (Rubinfeld and Sudan, 1996), deals with the following relaxation of decision problems: given a fixed property and an input x, one wants to decide whether x has the property or is being far from having the property. The main result here is that if G={g: {0, 1}/sup n//spl rarr/{0, 1}} is a family of Boolean functions that have read-once branching programs of width w, then for every n and /spl epsiv/>0 there is a randomized algorithm that always accepts every x/spl isin/{0, 1}/sup n/ if g(x)=1, and rejects it with height probability if at least /spl epsiv/n bits of x should be modified in order for it to be in g/sup -1/(1). The algorithm queries (2w//spl epsiv/)/sup 0(w)/ many queries. In particular, for constant /spl epsiv/ and w, the query complexity is 0(1). This generalizes the results of (Alon et al. , 1999) asserting that regular languages are efficiently (/spl epsiv/, O(1))-testable.

Details

FOCS Conference 1999 Conference Paper

Cuts, Trees and l 1 -Embeddings of Graphs

  • Anupam Gupta 0001
  • Ilan Newman
  • Yuri Rabinovich
  • Alistair Sinclair

Motivated by many recent algorithmic applications, the paper aims to promote a systematic study of the relationship between the topology of a graph and the metric distortion incurred where the graph is embedded into l/sub 1/ space. The main results are: 1. Explicit constant-distortion embeddings of all series parallel graphs, and all graphs with bounded Euler number. These are thus the first natural families known to have constant distortion (strictly greater than 1). Using the above embeddings, we obtain algorithms to approximate the sparsest cut in such graphs to within a constant factor. 2) A constant-distortion embedding of outerplanar graphs into the restricted class of l/sub 1/-metrics known as "dominating tree metrics". We also show a lower bound of /spl Omega/(log n) on the distortion for embeddings of series-parallel graphs into (distributions over) dominating tree metrics. This shows, surprisingly, that such metrics approximate distances very poorly even for families of graphs with low tree width, and excludes the possibility of using them to explore the finer structure of l/sub 1/-embeddability.

Details

FOCS Conference 1999 Conference Paper

Regular Languages Are Testable with a Constant Number of Queries

  • Noga Alon
  • Michael Krivelevich
  • Ilan Newman
  • Mario Szegedy

We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser and Ron (1996). The subject of this paper is testing regular languages. Our main result is as follows. For a regular language L/spl isin/{0, 1}* and an integer n there exists a randomized algorithm which always accepts a word w of length n if w/spl isin/L, and rejects it with high probability if w has to be modified in at least En positions to create a word in L. The algorithm queries O~(1//spl epsiv/) bits of w. This query complexity is shown to be optimal up to a factor poly-logarithmic in 1//spl epsiv/. We also discuss testability of more complex languages and show, in particular, that the query complexity required for testing context free languages cannot be bounded by any function of /spl epsiv/. The problem of testing regular languages can be viewed as a part of a very general approach, seeking to probe testability of properties defined by logical means.

Details

TCS Journal 1993 Journal Article

On read-once threshold formulae and their randomized decision tree complexity

  • Rafi Heiman
  • Ilan Newman
  • Avi Wigderson

TC0 is the class functions computable by polynomial-size, constant-depth formulae with threshold gates. Read-once TC 0 (RO-TC 0) is the subclass of TC0 which restricts every variable to occur exactly once in the formula. Our main result is a (tight) linear lower bound on the randomized decision tree complexity of any function in RO-TC0. This relationship between threshold circuits and decision trees bears significance on both models of computation. Regarding decision trees, this is the first class of functions for which such a strong bound is known. Regarding threshold circuits, it may be considered as a possible first step towards proving TC 0 ≠ NC 1; generalizing our lower bound to all functions in TC0 would establish this separation. Another structural result we obtain is that a read-once threshold formula uniquely represents the function it computes.

Details DOI

FOCS Conference 1991 Conference Paper

Search Problems in the Decision Tree Model (Preliminary Version)

  • László Lovász 0001
  • Moni Naor
  • Ilan Newman
  • Avi Wigderson

The relative power of determinism, randomness, and nondeterminism for search problems in the Boolean decision tree model is studied. It is shown that the CNF search problem is complete for all the variants of decision trees. It is then shown that the gaps between the nondeterministic, the randomized, and the deterministic complexities can be arbitrarily large for search problems. The special case of nondeterministic complexity is discussed. >

Details
v2026.09.13