Ilan Newman - RankMe

136 papers A* 23A 7B 4Misc 1Journal 78Unranked 19

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Debate is efficient with your time. CoRR Jonah Brown-Cohen, Geoffrey Irving, Simon C. Marshall, Ilan Newman, Georgios Piliouras, Mario Szegedy
2026	A*	`conf`	Testing forbidden order-pattern properties on hypergrids. SODA Harish Chandramouleeswaran, Ilan Newman, Tomer Pelleg, Nithin Varma
2025	J	`jnl`	Testing forbidden order-pattern properties on hypergrids. CoRR Harish Chandramouleeswaran, Ilan Newman, Tomer Pelleg, Nithin Varma
2024	A*	`conf`	Hardness Condensation by Restriction. STOC Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov
2024	J	`jnl`	Strongly Sublinear Algorithms for Testing Pattern Freeness. TheoretiCS Ilan Newman, Nithin Varma
2023	J	`jnl`	Hardness Condensation by Restriction. Electron. Colloquium Comput. Complex. Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov
2023	J	`jnl`	No Ascending Auction can find Equilibrium for SubModular valuations. CoRR Oren Ben-Zwi, Ilan Newman
2023	J	`jnl`	Online embedding of metrics. CoRR Ilan Newman, Yuri Rabinovich
2022	—	`conf`	Parameterized Convexity Testing. SOSA Abhiruk Lahiri, Ilan Newman, Nithin Varma
2022	—	`book`	Query Complexity Mario Szegedy, Ilan Newman, Troy Lee
2022	A*	`conf`	Strongly Sublinear Algorithms for Testing Pattern Freeness. ICALP Ilan Newman, Nithin Varma
2021	A*	`conf`	Coresets for Decision Trees of Signals. NeurIPS Ibrahim Jubran, Ernesto Evgeniy Sanches Shayda, Ilan Newman, Dan Feldman
2021	J	`jnl`	Coresets for Decision Trees of Signals. CoRR Ibrahim Jubran, Ernesto Evgeniy Sanches Shayda, Ilan Newman, Dan Feldman
2021	J	`jnl`	Hamiltonian and pseudo-Hamiltonian cycles and fillings in simplicial complexes. J. Comb. Theory B Rogers Mathew, Ilan Newman, Yuri Rabinovich, Deepak Rajendraprasad
2021	A*	`conf`	New Sublinear Algorithms and Lower Bounds for LIS Estimation. ICALP Ilan Newman, Nithin Varma
2021	J	`jnl`	Parameterized Convexity Testing. CoRR Abhiruk Lahiri, Ilan Newman, Nithin Varma
2021	J	`jnl`	Strongly Sublinear Algorithms for Testing Pattern Freeness. CoRR Ilan Newman, Nithin Varma
2020	J	`jnl`	New Algorithms and Lower Bounds for LIS Estimation. CoRR Ilan Newman, Nithin Varma
2020	J	`jnl`	On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs. Comput. Complex. Hiro Ito, Areej Khoury, Ilan Newman
2020	—	`conf`	Online Embedding of Metrics. SWAT Ilan Newman, Yuri Rabinovich
2019	J	`jnl`	Contractors' minimum spanning tree. Australas. J Comb. Irith Ben-Arroyo Hartman, Ilan Newman
2019	J	`jnl`	On the Characterization of 1-sided error Strongly-Testable Graph Properties for bounded-degree graphs, including an appendix. CoRR Hiro Ito, Areej Khoury, Ilan Newman
2019	J	`jnl`	Testing for forbidden order patterns in an array. Random Struct. Algorithms Ilan Newman, Yuri Rabinovich, Deepak Rajendraprasad, Christian Sohler
2017	A*	`conf`	Testing for Forbidden Order Patterns in an Array. SODA Ilan Newman, Yuri Rabinovich, Deepak Rajendraprasad, Christian Sohler
2016	—	`conf`	Every Property of Outerplanar Graphs is Testable. APPROX-RANDOM Jasine Babu, Areej Khoury, Ilan Newman
2015	J	`jnl`	Hats, auctions and derandomization. Random Struct. Algorithms Oren Ben-Zwi, Ilan Newman, Guy Wolfovitz
2013	J	`jnl`	Ascending auctions and Walrasian equilibrium CoRR Oren Ben-Zwi, Ron Lavi, Ilan Newman
2013	J	`jnl`	Every Property of Hyperfinite Graphs Is Testable. SIAM J. Comput. Ilan Newman, Christian Sohler
2013	J	`jnl`	On Multiplicative Lambda-Approximations and Some Geometric Applications. SIAM J. Comput. Ilan Newman, Yuri Rabinovich
2013	J	`jnl`	The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs. J. Comb. Optim. Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Ilan Newman, Oren Weimann
2012	J	`jnl`	Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs. Discret. Comput. Geom. Victor Chepoi, Feodor F. Dragan, Ilan Newman, Yuri Rabinovich, Yann Vaxès
2012	J	`jnl`	Hierarchy Theorems for Property Testing. Comput. Complex. Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg
2012	J	`jnl`	Local Versus Global Properties of Metric Spaces. SIAM J. Comput. Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh S. Vempala
2012	A*	`conf`	On multiplicative λ-approximations and some geometric applications. SODA Ilan Newman, Yuri Rabinovich
2012	J	`jnl`	On the query complexity of testing orientations for being Eulerian. ACM Trans. Algorithms Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman, Orly Yahalom
2011	J	`jnl`	Applying Property Testing to an Image Partitioning Problem. IEEE Trans. Pattern Anal. Mach. Intell. Igor Kleiner, Daniel Keren, Ilan Newman, Oren Ben-Zwi
2011	A*	`conf`	Every property of hyperfinite graphs is testable. STOC Ilan Newman, Christian Sohler
2011	J	`jnl`	LCS approximation via embedding into locally non-repetitive strings. Inf. Comput. Gad M. Landau, Avivit Levy, Ilan Newman
2011	J	`jnl`	Optimal Bi-Valued Auctions CoRR Oren Ben-Zwi, Ilan Newman
2011	J	`jnl`	Testing Periodicity. Algorithmica Oded Lachish, Ilan Newman
2011	J	`jnl`	The Stackelberg Minimum Spanning Tree Game. Algorithmica Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, Oren Weimann
2011	J	`jnl`	Treewidth governs the complexity of target set selection. Discret. Optim. Oren Ben-Zwi, Danny Hermelin, Daniel Lokshtanov, Ilan Newman
2010	—	`conf`	Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs. APPROX-RANDOM Victor Chepoi, Feodor F. Dragan, Ilan Newman, Yuri Rabinovich, Yann Vaxès
2010	J	`jnl`	Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs CoRR Victor Chepoi, Feodor F. Dragan, Ilan Newman, Yuri Rabinovich, Yann Vaxès
2010	—	`ch.`	Hierarchy Theorems for Property Testing. Property Testing Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg
2010	J	`jnl`	On Cut Dimension of ℓ CoRR Ilan Newman, Yuri Rabinovich
2010	—	`ch.`	Property Testing of Massively Parametrized Problems - A Survey. Property Testing Ilan Newman
2009	J	`jnl`	A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity. SIAM J. Comput. Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira
2009	B	`conf`	A New Derandomization of Auctions. SAGT Oren Ben-Zwi, Ilan Newman, Guy Wolfovitz
2009	A*	`conf`	An exact almost optimal algorithm for target set selection in social networks. EC Oren Ben-Zwi, Danny Hermelin, Daniel Lokshtanov, Ilan Newman
2009	J	`jnl`	Computing in fault tolerant broadcast networks and noisy decision trees. Random Struct. Algorithms Ilan Newman
2009	J	`jnl`	Hard Metrics from Cayley Graphs of Abelian Groups. Theory Comput. Ilan Newman, Yuri Rabinovich
2009	—	`conf`	Hierarchy Theorems for Property Testing. APPROX-RANDOM Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg
2009	B	`conf`	LCS Approximation via Embedding into Local Non-repetitive Strings. CPM Gad M. Landau, Avivit Levy, Ilan Newman
2009	J	`jnl`	The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs CoRR Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Ilan Newman, Oren Weimann
2009	—	`conf`	The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs. WINE Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Ilan Newman, Oren Weimann
2008	—	`conf`	Complementing Missing and Inaccurate Profiling Using a Minimum Cost Circulation Algorithm. HiPEAC Roy Levin, Ilan Newman, Gadi Haber
2008	J	`jnl`	Hierarchy Theorems for Property Testing. Electron. Colloquium Comput. Complex. Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg
2008	—	`conf`	On the Query Complexity of Testing Orientations for Being Eulerian. APPROX-RANDOM Eldar Fischer, Oded Lachish, Ilan Newman, Arie Matsliah, Orly Yahalom
2008	J	`jnl`	Quantum Property Testing. SIAM J. Comput. Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig
2008	J	`jnl`	Space Complexity Vs. Query Complexity. Comput. Complex. Oded Lachish, Ilan Newman, Asaf Shapira
2007	J	`jnl`	Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs. SIAM J. Comput. Noga Alon, Eldar Fischer, Ilan Newman
2007	A	`conf`	Hard Metrics from Cayley Graphs of Abelian Groups. STACS Ilan Newman, Yuri Rabinovich
2007	J	`jnl`	Lower bounds for testing Euclidean Minimum Spanning Trees. Inf. Process. Lett. Oren Ben-Zwi, Oded Lachish, Ilan Newman
2007	J	`jnl`	Partitioning multi-dimensional sets in a small number of "uniform" parts. Eur. J. Comb. Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai K. Vereshchagin
2007	J	`jnl`	Robust Polynomials and Quantum Algorithms. Theory Comput. Syst. Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf
2007	—	`conf`	Testing APPROX-RANDOM Sourav Chakraborty, Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman
2007	A	`conf`	Testing Properties of Constraint-Graphs. CCC Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur
2007	J	`jnl`	Testing Properties of Constraint-Graphs. Electron. Colloquium Comput. Complex. Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur
2007	J	`jnl`	Testing of matrix-poset properties. Comb. Eldar Fischer, Ilan Newman
2007	J	`jnl`	Testing versus Estimation of Graph Properties. SIAM J. Comput. Eldar Fischer, Ilan Newman
2007	J	`jnl`	The Stackelberg Minimum Spanning Tree Game CoRR Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, Oren Weimann
2007	B	`conf`	The Stackelberg Minimum Spanning Tree Game. WADS Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, Oren Weimann
2006	A*	`conf`	A combinatorial characterization of the testable graph properties: it's all about regularity. STOC Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira
2006	J	`jnl`	Embedding SIAM J. Discret. Math. Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair
2006	A*	`conf`	Local versus global properties of metric spaces. SODA Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh S. Vempala
2006	—	`conf`	Space Complexity vs. Query Complexity. APPROX-RANDOM Oded Lachish, Ilan Newman, Asaf Shapira
2006	J	`jnl`	Space Complexity vs. Query Complexity. Electron. Colloquium Comput. Complex. Oded Lachish, Ilan Newman, Asaf Shapira
2005	J	`jnl`	Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time. SIAM J. Comput. Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler
2005	A	`conf`	Increasing Kolmogorov Complexity. STACS Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin
2005	J	`jnl`	Languages that are Recognized by Simple Counter Automata are not necessarily Testable Electron. Colloquium Comput. Complex. Oded Lachish, Ilan Newman
2005	J	`jnl`	Partitioning multi-dimensional sets in a small number of "uniform" parts Electron. Colloquium Comput. Complex. Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai K. Vereshchagin
2005	A	`conf`	Robust Polynomials and Quantum Algorithms. STACS Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf
2005	J	`jnl`	Testing Orientation Properties Electron. Colloquium Comput. Complex. Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur
2005	—	`conf`	Testing Periodicity. APPROX-RANDOM Oded Lachish, Ilan Newman
2005	A*	`conf`	Testing versus estimation of graph properties. STOC Eldar Fischer, Ilan Newman
2004	A	`conf`	Computing in Fault Tolerance Broadcast Networks. CCC Ilan Newman
2004	J	`jnl`	Cuts, Trees and l Comb. Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair
2004	J	`jnl`	Functions that have read-twice constant width branching programs are not necessarily testable. Random Struct. Algorithms Eldar Fischer, Ilan Newman, Jirí Sgall
2004	J	`jnl`	Increasing Kolmogorov Complexity Electron. Colloquium Comput. Complex. Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin
2004	J	`jnl`	Testing Periodicity Electron. Colloquium Comput. Complex. Oded Lachish, Ilan Newman
2003	A*	`conf`	Embedding k-outerplanar graphs into l1. SODA Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair
2003	A*	`conf`	Quantum property testing. SODA Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig
2003	J	`jnl`	Robust Quantum Algorithms and Polynomials CoRR Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf
2003	A*	`conf`	Sublinear-time approximation of Euclidean minimum spanning tree. SODA Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler
2002	—	`conf`	A lower bound on the distortion of embedding planar metrics into Euclidean space. SCG Ilan Newman, Yuri Rabinovich
2002	J	`jnl`	Communication - Processor Tradeoffs in a Limited Resources PRAM. Algorithmica Adnan Agbaria, Yosi Ben-Asher, Ilan Newman
2002	A	`conf`	Functions that have Read-Twice Constant Width Branching Programs are not Necessarily Testable. CCC Eldar Fischer, Ilan Newman
2002	A*	`conf`	Monotonicity testing over general poset domains. STOC Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky
2002	J	`jnl`	Testing Membership in Languages that Have Small Width Branching Programs. SIAM J. Comput. Ilan Newman
2001	A*	`conf`	Testing of matrix properties. STOC Eldar Fischer, Ilan Newman
2000	J	`jnl`	Regular Languages are Testable with a Constant Number of Queries. SIAM J. Comput. Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy
2000	J	`jnl`	Self-Simulation for the Passive Optical Star. J. Algorithms Pascal Berthomé, Torben Hagerup, Ilan Newman, Assaf Schuster
2000	A*	`conf`	Testing of Functions that have small width Branching Programs. FOCS Ilan Newman
1999	B	`conf`	Communication-Processor Tradeoffs in Limited Resources PRAM. SPAA Adnan Agbaria, Yosi Ben-Asher, Ilan Newman
1999	A*	`conf`	Cuts, Trees and l FOCS Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair
1999	J	`jnl`	Optimal Search in Trees. SIAM J. Comput. Yosi Ben-Asher, Eitan Farchi, Ilan Newman
1999	A*	`conf`	Regular Languages Are Testable with a Constant Number of Queries. FOCS Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy
1998	Misc	`conf`	Broadcasting on a budget in the multi-service communication model. HiPC Gene Itkis, Ilan Newman, Assaf Schuster
1997	J	`jnl`	Geometric Approach for Optimal Routing on a Mesh with Buses. J. Comput. Syst. Sci. Yosi Ben-Asher, Ilan Newman
1997	A*	`conf`	Optimal Search in Trees: Extended Abstract + Appendix. SODA Yosi Ben-Asher, Eitan Farchi, Ilan Newman
1997	J	`jnl`	Randomized Single-Target Hot-Potato Routing. J. Algorithms Ishai Ben-Aroya, Ilan Newman, Assaf Schuster
1996	J	`jnl`	Geometric Approach for Optimal Routing on Mesh with Buses Electron. Colloquium Comput. Complex. Yosi Ben-Asher, Ilan Newman
1996	J	`jnl`	Optimal Search in Trees Electron. Colloquium Comput. Complex. Yosi Ben-Asher, Ilan Newman
1996	A*	`conf`	Public vs. Private Coin Flips in One Round Communication Games (Extended Abstract). STOC Ilan Newman, Mario Szegedy
1995	—	`conf`	Decision Trees with AND, OR Queries. SCT Yosi Ben-Asher, Ilan Newman
1995	J	`jnl`	Decision Trees with Boolean Threshold Queries. J. Comput. Syst. Sci. Yosi Ben-Asher, Ilan Newman
1995	—	`conf`	Geometric approach for optimal routing on mesh with buses. SPDP Yosi Ben-Asher, Ilan Newman
1995	J	`jnl`	Hot Potato Worm Routing via Store-and-Forward Packet Routing. J. Parallel Distributed Comput. Ilan Newman, Assaf Schuster
1995	J	`jnl`	Hot-Potato Algorithms for Permutation Routing. IEEE Trans. Parallel Distributed Syst. Ilan Newman, Assaf Schuster
1995	J	`jnl`	Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy. SIAM J. Discret. Math. Ilan Newman, Avi Wigderson
1995	—	`conf`	Randomized Single-Target Hot-Potato Routing. ISTCS Ishai Ben-Aroya, Ilan Newman, Assaf Schuster
1995	J	`jnl`	Search Problems in the Decision Tree Model. SIAM J. Discret. Math. László Lovász, Moni Naor, Ilan Newman, Avi Wigderson
1995	A	`conf`	Self-Simulation for the Passive Optical Star Model. ESA Pascal Berthomé, Th. Duboux, Torben Hagerup, Ilan Newman, Assaf Schuster
1994	J	`jnl`	Non-Deterministic Communication Complexity with Few Witnesses. J. Comput. Syst. Sci. Mauricio Karchmer, Ilan Newman, Michael E. Saks, Avi Wigderson
1993	J	`jnl`	Combinatorial characterization of read-once formulae. Discret. Math. Mauricio Karchmer, Nathan Linial, Ilan Newman, Michael E. Saks, Avi Wigderson
1993	—	`conf`	Hot-Potato Worm Routing is Almost as Easy as Store-and-Forward Packet Routing. ISTCS Ilan Newman, Assaf Schuster
1993	J	`jnl`	On Read-Once Threshold Formulae and Their Randomized Decision in Tree Complexity. Theor. Comput. Sci. Rafi Heiman, Ilan Newman, Avi Wigderson
1992	—	`conf`	Non-deterministic Communication Complexity with Few Witness. SCT Mauricio Karchmer, Ilan Newman, Michael E. Saks, Avi Wigderson
1991	J	`jnl`	On grid intersection graphs. Discret. Math. Irith Ben-Arroyo Hartman, Ilan Newman, Ran Ziv
1991	—	`—`	On the formula complexity of simple Boolean functions (על סבוכיות הנסחא של פונקציות בוליאניות פשוטות.). Ilan Newman
1991	J	`jnl`	Private vs. Common Random Bits in Communication Complexity. Inf. Process. Lett. Ilan Newman
1991	A*	`conf`	Search Problems in the Decision Tree Model (Preliminary Version) FOCS László Lovász, Moni Naor, Ilan Newman, Avi Wigderson
1990	J	`jnl`	Approximation algorithms for covering a graph by vertex-disjoint paths of maximum total weight. Networks Shlomo Moran, Ilan Newman, Yaron Wolfstahl
1990	—	`conf`	On Read-Once Threshold Formulae and Their Randomized Decision Tree Complexity. SCT Rafi Heiman, Ilan Newman, Avi Wigderson
1990	—	`conf`	Perfect Hashing, Graph Entropy, and Circuit Complexity. SCT Ilan Newman, Prabhakar Ragde, Avi Wigderson