GUY EVEN
List of Publications
- ``Construction of Small Probabilistic Spaces for Deterministic
Simulation,'' supervisor Prof. Oded Goldreich, 1991 (master's
thesis).
- ``Design of VLSI Circuits Using
Retiming,''
supervisors Prof. Benny Chor and Dr. Ami Litman, 1994 (doctoral
dissertation).
- Guy Even and Moti Medina, Logic Design: A Rigorous
Approach, Cambridge Univ. Press, Oct. 2012.
- Shimon Even, Graph Algorithms, 2nd edition, Cambridge
Univ. Press, 2011.
- Guy Even and Magnus M. Halldorsson: Structural Information and
Communication Complexity, 19th International Colloquium, SIROCCO
2012, Reykjavik, Iceland, June 30-July 2, 2012, LNCS 7355, Springer
2012.
- Guy Even and Dror Rawitz: Design and Analysis of Algorithms,
Proceedings of the First Mediterranean conference on Design and
Analysis of Algorithms, MedAlg 2012, Kibbutz Ein Gedi, Israel, Dec.
2012, LNCS 7659, Springer 2012.
- Guy Even, Ophir Rachman and Ilan
Spillinger, ``Linear Test Sequences for Detecting
Functionally Faulty RAM's'', Integration, The VLSI Journal, Vol. 16, No. 1, pp. 75-89, 1993.
- Ran Canetti, Guy Even and Oded Goldreich, ``Lower
bounds on sampling algorithms for estimating the average
'',
Information Processing Letters, 53:17-25, 1995.
- Guy Even, Ilan Spillinger and Leon Stok, ``Retiming
Revisited and Reversed,''
IEEE Transactions on Computer-Aided Design of Integrated Circuits
and Systems, Vol. 15, No. 3, March 1996.
- Guy Even,``The Retiming Lemma : A Simple Proof and
Applications
,''
Integration, The VLSI Journal, Vol. 20, No. 2, pp. 123-137, March 1996.
- Guy Even, ``Real-Time Iterative Systolic Integer
Multiplier,''
Integration, The VLSI Journal, Vol. 22, No. 1-2, pp. 23-38, 1997.
- Michael Braun, Guy Even, and Thomas Walle,
``Mirroring: A Technique for Pipelining of Semi-Systolic and Systolic
Arrays,''
Integration, The VLSI Journal,
Vol. 23, pp. 115-130, 1997.
- Guy Even and Ami Litman, ``Overcoming Chip-to-Chip
Delays and Clock Skews,''
Integration, The VLSI Journal, Vol. 24, pp. 119-133, 1997.
- Guy Even, Seffi Naor, Baruch Schieber, and Madhu Sudan,
``Approximating Minimum Feedback Sets and
Multi-Cuts in Directed
Graphs,''
Algorithmica, 20 : 151-174, 1998.
- G. Even, O. Goldreich, M. Luby, N. Nisan and B.
Velickovic, ``Efficient Approximation of Product
Distributions
,'' Random Structures & Algorithms, Volume 13, Issue 1, pp.
1-16, August 1998,
- Guy Even, Seffi Naor, Baruch Schieber and Satish Rao,
``Fast Approximate Graph Partitioning Algorithms,''
SIAM Journal on Computing.
Volume 28, Number 6,
pp. 2187-2214, 1999.
- Guy Even and Shimon Even, ``Embedding
Interconnection Networks in Grids via the Layered Cross
Product'',
Networks, Volume 36, Issue 2, pp. 91-95, 2000.
- Asger Munk Nielsen, David W. Matula, C. N. Lyu, and Guy Even,
``An IEEE compliant floating-point adder that
conforms with the pipelined packet-forwarding
paradigm,'' IEEE
Transactions on Computers, Vol. 49, No. 1, pp. 33-47, January 2000.
- Guy Even, Seffi Naor, Baruch Schieber and Satish Rao,
``Divide-and-Conquer Approximation Algorithms Via
Spreading Metrics,'' Journal of the ACM, Volume 47, No. 4, pp. 585 - 616, Jul. 2000.
- Guy Even, Seffi Naor, Baruch Schieber and Leonid Zosin,
``Approximating Minimum Subset Feedback Sets in
Undirected Graphs with Applications to
Multicuts,''
SIAM Journal on Discrete Math, Vol. 13 No. 2, pp. 255-267, 2000.
- Guy Even and Wolfgang Paul, ``On the design of IEEE
compliant floating point
units,'' IEEE
Transactions on Computers, Vol. 49, No. 5, pp. 398-413, May 2000.
- Guy Even and Peter-M. Seidel, ``A comparison of
three rounding algorithms for IEEE floating-point multiplication
,''
IEEE Trans. on
Computers, Special issue on Computer Arithmetic, Vol. 49, No. 7, pp.
638-650, July 2000.
There is a mistake in Fig. 4 in the paper (Thanks to Eran Eidiniger
for pointing out this mistake).
A corrected figure.
- Guy Even, Seffi Naor and Leonid Zosin,
``An 8-Approximation Algorithm for the Subset
Feedback Vertex Set Problem
'',
SIAM Journal on Computing.
Volume 30, Number 4,
pp. 1231-1252, 2000.
- Guy Even, Silvia M. Müller, and Peter-Michael Seidel,
``A Dual Precision IEEE Floating-Point Multiplier'',
Integration, The VLSI Journal,
Volume 29, Issue 2, pp. 167-180, September 2000.
- Reuven Bar-Yehuda, Guy Even, Jon Feldman and Seffi Naor,
``Computing an optimal orientation of a balanced decomposition tree
for linear arrangement problems'',
Journal of Graph Algorithms and Applications,
Vol. 5, no. 4, pp. 1-27, 2001.
- Guy Even, Sudipto Guha, and Baruch Schieber,
``Improved Approximations of Crossings in Graph
Drawings and VLSI Layout
Areas,"
SIAM Journal on Computing,
Vol. 32, No. 1, pp. 231-252, 2003.
- Peter-M. Seidel and Guy Even,
``Delay-Optimized Implementation of IEEE
Floating-Point
Addition'',
IEEE Transactions on Computers, pp. 97-113, Vol. 53, no. 2, February
2004.
- Shahar Bar-Or, Guy Even, and Yariv Levin,
``Generation of representative input vectors for
parametric designs: from low precision to high
precision'',
Integration, the VLSI journal, Vol. 36, Issues 1-2 ,
pp. 69-82, September, 2003.
- Guy Even, Zvi Lotker, Dana Ron, and Shakhar
Smorodinsky, ``Conflict-Free Colorings of Simple
Geometric Regions with Applications to Frequency Assignment in
Cellular
Networks'',
SIAM Journal on Computing, Vol. 33, No. 1, pp. 94-136, 2003.
- Guy Even, Naveen Garg, Jochen Könemann, R.
Ravi, and Amitabh Sinha, ``Covering Graphs using
Trees and Stars'',
Operations Research Letters, Vol. 32/4, pp. 309-315, 2004.
- Reuven Bar-Yehuda, Guy Even, and Shimon (Moni)
Shahar, ``On Approximating A Geometric
Prize-Collecting Traveling Salesman Problem With Time
Windows'',
Journal of Algorithms,Vol 55/1, pp. 76-92, 2005.
- Guy Even, Guy Kortsarz, and Wolfgang Slany,
``On network design problems: fixed cost flows
and the Covering Steiner
Problem
Transactions on Algorithms,
Volume 1 , Issue 1,
pp. 74 - 101, July 2005.
- Guy Even, Peter-Michael Seidel, and Warren
Ferguson, ``A Parametric Error Analysis of
Goldschmidt's Division
Algorithm``,
Journal of Computer and System Sciences, Volume 70, Issue 1,
pages 118-139. Feb. 2005.
- Nissim Halabi and Guy Even, ``Improved bounds
on the word error probability of RA(2) codes with linear
programming based
decoding'',
IEEE Transactions on Information Theory, 51:1, pp. 265- 280, Jan.
2005.
- Guy Even, Dror Rawitz, and Shimon (Moni) Shahar,
``Hitting sets when the VC-dimension is
small,
Information Processing Letters,
Vol. 95, Issue 2 , pp. 358-362, July 2005.
- Chandra Chekuri, Guy Even and Guy Kortsarz,
``A combinatorial approximation algorithm for the
group Steiner
problem'',
Discrete Applied Mathematics, Volume 154, Issue 1, pp. 15-34,
Jan. 2006.
- Guy Even and Retsef Levi and Dror Rawitz and Baruch Schieber and
Shimon Shahar and Maxim Sviridenko ``Algorithms
for Capacitated Rectangle Stabbing and Lot Sizing with Joint
Set-Up
Costs,
ACM Trans. Algorithms, Volume 4, Number 3, pp. 1-17, 2008.
- Guy Even, Magnús M. Halldórsson, Lotem Kaplan, and Dana Ron,
``Scheduling with Conflicts: Online and Offline
Algorithms'',
J. on Scheduling: Volume 12, Issue 2 (2009), pp. 199-224.
- Guy Even, Jon Feldman, Guy Kortsarz, and Zeev
Nutov, ``A 1.8-approximation algorithm for augmenting the
edge-connectivity of a graph from 1 to 2'',
ACM Transactions on Algorithms,
Volume 5 , Issue 2 (March 2009).
- Alexander Zadorojniy, Guy Even, and Adam Shwartz,
``A strongly polynomial algorithm for controlled queues'',
Mathematics of Operations Research, articles in advance (Oct. 7, 2009).
- Guy Even, Tamir Levi, and Ami Litman,
``Optimal conclusive sets for comparator
networks'',
Theor. Comput. Sci., 410(14): 1369-1376, 2009.
- Chandra Chekuri, Guy Even, Anupam Gupta, and Danny Segev,
``Set Connectivity Problems in Undirected Graphs
and the Directed Steiner Network
Problem'', ACM
Transactions on Algorithms, Vol. 7, Issue 2, pp. 18:1-18:7, 2011.
- Nissim Halabi and Guy Even, LP Decoding of Regular LDPC Codes in
Memoryless Channels, IEEE Transactions on Information Theory
(Special issue dedicated to Ralf Koetter) 57(2): 887-897 (2011).
- Guy Even, Guy Kortsarz, Zeev Nutov, A 1.5-approximation
algorithm for augmenting edge-connectivity of a graph from 1 to 2.
Inf. Process. Lett. 111(6): 296-300 (2011)
- Guy Even and Moti Medina, Parallel Randomized
Load Balancing: A Lower Bound for a More General Model, Theor. Comput. Sci.
412(22): 2398-2408 (2011)
- Guy Even and Moti Medina, Revisiting
Randomized Parallel Load Balancing Algorithms
, special
issue of SIROCCO 2009 in TCS. Volume 444, Pages 87 99, 27 July 2012.
- Guy Even and Alexander Zadorojniy, "Strong
Polynomiality of the Gass-Saaty Shadow-Vertex Pivoting Rule for
Controlled Random
Walks",
Annals of Operations Research,
Volume 201, Issue 1, pp 159-167,
December 2012.
- Guy Even, Moti Medina, Stefan Schmid, and Gregor Schaffrath,
Competitive and Deterministic Embeddings of Virtual Networks,
accepted to 2012 ICDCN special issue in TCS.
- Dmitriy Laschov, Michael Margaliot, and Guy Even, "Observability of
Boolean Networks: A Graph-Theoretic Approach", accepted to Automatica, April 2013.
- Guy Even and Nissim Halabi, ``Local-Optimality Guarantees for
Optimal Decoding Based on Paths'', accepted to SIAM Journal on
Discrete Math, 2013.
- Nissim Halabi and Guy Even, "On Decoding
Irregular Tanner Codes with Local-Optimality
Guaranties", accepted to IEEE
trans. on Information Theory, 2013.
- Guy Even and Shakhar Smorodinsky,
"Hitting Sets Online and Unique-Max Coloring" submitted to SIAM Journal on Computing, 12-7-2012.
- Guy Even, Yaniv Fais, Moti Medina, Shimon Shahar, Alexander Zadorojniy: Real-Time Video Streaming in Multi-hop Wireless Static Ad Hoc Networks, CoRR abs/1104.0779, 2011.
- Guy Even, Yakov Matsri, Moti Medina: Multi-Hop Routing and
Scheduling in Wireless Networks in the SINR model, CoRR
abs/1104.1330, 2011.
- Guy Even and Nissim Halabi, ``Message-Passing Algorithms for Packing and Covering Linear Programs with Zero-One Matrices'', arXiv preprint arXiv:1302.3518, 2013.
- G. Even, ``On Teaching Fast Adder Designs:
Revisiting Ladner &
Fischer'',
in Theoretical Computer Science: Essays in Memory of Shimon
Even, Editors: Oded Goldreich, Arnold L. Rosenberg, Alan L.
Selman, Springer's
LNCS
Festschrift series, Vol
3895, pp. 313-347, 2006.
- G. Even, ``Recursive Greedy
Methods'',
Chap. 5 in Handbook of Approximation Algorithms and
Metaheuristics, edited by Teofilo F. Gonzalez, Chapman &
Hall/CRC Computer & Information Science Series, 2007.
- Guy Even, Oded Goldreich, Mike Luby, Noam Nisan, Boban Velickovic,
``Approximations of General Independent Distributions (extended
abstract)'', Proceedings of the 24th Annual ACM Symposium on
Theory of Computing, pp. 10-16, May 1992.
- Guy Even, Seffi Naor, Baruch Schieber and Madhu Sudan, ``Approximating
Minimum Feedback Sets and Multi-Cuts in Directed Graphs (extended
abstract),'' Proceedings of the 4th MPS Conference on Integer
Programming and Combinatorial Optimization (IPCO), pp. 14-28, 1995.
- Guy Even, Seffi Naor, Baruch Schieber and Satish Rao,
``Divide-and-Conquer Approximation Algorithms Via Spreading Metrics,''
(Extended Abstract), Proceedings of the
36th IEEE Conference on Foundations of Computer Science, Milwaukee,
Wisconsin, (1995), pp. 62-71.
- Guy Even, Seffi Naor, Baruch Schieber and Leonid Zosin,
``Approximating Minimum Subset Feedback Sets in Undirected Graphs with
Applications to Multicuts (extended abstract),'' Proceedings of
the Fourth Israel Symposium on Theory of Computing and Systems,
Jerusalem, Israel, June 10-12, 1996, pp. 78-88.
- Guy Even and Ami Litman, ``Overcoming Chip-to-Chip Delays and Clock
Skews (extended abstract),'' Proceedings of the International
Conference on Application-specific Systems, Architectures and
Processors (ASAP'96) - Poster Session, Chicago, August 19-21, 1996,
pp. 199-208.
- Guy Even, Seffi Naor and Leonid Zosin, ``An
8-Approximation Algorithm for the Subset Feedback Vertex Set
Problem'',
Proceedings of the 37th IEEE Conference on Foundations of
Computer Science, Burlington, Vermont, 14-16 October, 1996,
pp. 310-319.
- Guy Even, Seffi Naor, Baruch Schieber and Satish Rao,
``Fast Approximate Graph Partitioning Algorithms,''
Eighth Annual ACM-SIAM Symp. on Discrete Algorithms, Jan. 1997.
- Guy Even and Shimon Even, ``Embedding
Interconnection Networks in Grids via the Layered Cross Product''. Invited
paper in Algorithms and Complexity, Third Italian Conference,
CIAC'97, Rome, Italy, March 1997, Proceedings, Giacarlo Bongiovanni,
Daniel Pierre Bovet and Giuseppe Di Battista (Eds.), Springer, 1997,
LNCS Vol. 1203, pp. 3-12.
- Asger Munk Nielsen, David W. Matula, C. N. Lyu, and Guy Even, ``Pipelined
packet-forwarding floating point: II. An Adder,'' 13th IEEE Symposium on Computer Arithmetic, Asilomar, California, July 6-9,
1997, pp. 148-155.
- Guy Even and Wolfgang Paul, ``On the design of IEEE compliant floating
point units,'' 13th IEEE Symposium on Computer
Arithmetic, Asilomar, California, July 6-9, 1997, pp. 54-63.
- Guy Even, Silvia M. Mueller, and Peter-Michael Seidel, ``A Dual Mode
IEEE Multiplier,'' Proceedings 2nd
IEEE International Conference on
Innovative Systems in Silicon (ISIS'97), pp. 282-289, 1997.
- Peter-M. Seidel and Guy Even, ``How many logic levels does
floating-point addition require?'' Proceedings of the 1998
International Conference on Computer Design (ICCD'98)): VLSI in
Computers & Processors, pp. 142-149, Austin, Texas, Oct. 1998.
- Guy Even and Peter-M. Seidel, ``A comparison of three rounding
algorithms for IEEE floating-point multiplication,'' in Proceedings 14th IEEE Symposium on Computer Arithmetic, pp.
225-232, Adelaide, Australia, April 14-16, 1999.
- Guy Even, Sudipto Guha, and Baruch Schieber, ``Improved
Approximations of Crossings in Graph Drawings and VLSI Layout
Areas," STOC 2000, pp. 296-305.
- Peter-M. Seidel and Guy Even, ``On the design of fast IEEE
Floating-Point Adders'', in Proceedings 15th IEEE Symposium on
Computer Arithmetic, pp. 184 -194, 2001.
- Guy Even, Jon Feldman, Guy Kortsarz, and
Zeev Nutov, ``A 3/2-approximation algorithm for
augmenting the edge-connectivity of a graph from 1 to 2 using a
given edge set'',
Michel X. Goemans, Klaus Jansen, José D. P. Rolim, Luca Trevisan
(Eds.), Proceedings of APPROX 2001, Lecture Notes in Computer
Science 2129, Springer, pp. 90-101, 2001.
- Guy Even and Guy Kortsarz, ``An approximation
algorithm for the Group Steiner
Problem'',
Proceedings of the thirteenth annual ACM-SIAM Symposium on Discrete
Algorithms (SODA-02), pp. 49 - 58, 2002.
- Guy Even, Guy Kortsarz, and Wolfgang Slany,
``On network design problems: fixed cost flows
and the Covering Steiner Problem'',
SWAT 2002, LNCS 2368, pp.
318-327, Springer, 2002.
- Guy Even, Zvi Lotker, Dana Ron, and Shakhar Smorodinsky,
``Conflict-Free Colorings of Simple Geometric Regions with
Applications to Frequency Assignment in Cellular Networks'', The
43rd Annual IEEE Symposium on Foundations of Computer Science
(FOCS'02), Vancouver, pp. 691-700, November 16 - 19, 2002
- Guy Even, Peter-Michael Seidel, and Warren Ferguson, ``A
Parametric Error Analysis of Goldschmidt's Division Algorithm``, in
the Proceedings of the 16th IEEE Symposium on Computer Arithmetic,
pp. 165-171, 2003.
- Guy Even, Naveen Garg, Jochen Könemann, R. Ravi, and Amitabh
Sinha, ``Covering Graphs using Trees and
Stars'', in APPROX 2003, Lecture Notes in
Computer Science , Vol. 2764, Springer, 2003.
- Reuven Bar-Yehuda, Guy Even, and Shimon (Moni) Shahar,
``On Approximating A Geometric Prize-Collecting
Traveling Salesman Problem With Time
Windows'', in ESA-2003, Lecture Notes in
Computer Science Volume 2832, pp. 55 - 66, Springer, 2003.
- Guy Even and Peter-M. Seidel,
Pipelined Multiplicative Division with IEEE Rounding,
in proceedings of ICCD-03, pp. 240-245, Oct. 2003.
- Guy Even and Nissim Halabi , Improved bounds
on the word error probability of RA(2) codes with linear
programming based decoding, presented in
Forty-First Annual Allerton Conference On Communication, Control,
And Computing, 2003.
- Guy Even and Dror Rawitz and Shimon (Moni) Shahar,
Approximation Algorithms for Capacitated Rectangle Stabbing,
accepted to the 6th Conference on Algorithms and Complexity (CIAC '06),
May 29-31, 2006. Rome, Italy.
- Guy Even and Moni Shahar, Scheduling of smart
antennas: capacitated coloring of unit circular-arc graphs,
,
Third Workshop on Combinatorial and Algorithmic Aspects of
Networking (CAAN 2006), 2 July, 2006. Chester, United Kingdom.
- Guy Even and Tamir Levi and Ami Litman,
Optimal Conclusive Sets for Comparator
Networks, 14th International
Colloquium on Structural Information and Communication Complexity
(SIROCCO 2007), Castiglioncello (LI), Italy, June 5-8, 2007.
- Ronen Goldberg and Guy Even and Peter-M. Seidel,
``An FPGA implementation of pipelined multiplicative division
with IEEE Rounding'', Fifteenth Annual IEEE Symposium
on Field-Programmable Custom Computing Machines (FCCM'07), Napa
Valley, CA, April 23-25, 2007.
- Chandra Chekuri, Guy Even, Anupam Gupta, and Danny Segev ``Set
Connectivity Problems in Undirected Graphs and the Directed Steiner
Network Problem'', Proceedings of the nineteenth annual ACM-SIAM
Symposium on Discrete Algorithms (SODA'08), pp. 532-541, 2008.
- Shai Erez and Guy Even,
``An Improved Micro-Architecture for
Function Approximation Using Piecewise Quadratic Interpolation,''
26th IEEE International Conference on Computer (ICCD-08), October
12-15, 2008.
- Guy Even and Moti Medina,
``Revisiting Randomized Parallel Load Balancing Algorithms'',
16th International Colloquium on Structural Information
and Communication Complexity (SIROCCO 2009),
May 25-27, 2009.
- Guy Even and Moti Medina, Parallel Randomized Load Balancing
Algorithms: A Lower Bound for a More General Model, 36th
International Conference on Current Trends in Theory and Practice of
Computer Science (SOFSEM 2010), January 23-29, 2010.
- Nissim Halabi and Guy Even, LP Decoding of Regular LDPC Codes in
Memoryless Channels, in proceedings of 2010 IEEE International
Symposium on Information Theory (ISIT), pp. 744 -748, 2010.
- Guy Even and Moti Medina, An O(log n)-Competitive Online
Centralized Randomized Packet-Routing Algorithm for Lines, in ICALP
2010: 37th International Colloquium on Automata, Languages and
Programming, Lecture Notes in Computer Science, Vol. 6199,
Springer, 2010.
- Guy Even and Moti Medina, Online Packet-Routing in Grids with
Bounded Buffers, SPAA 2011: Proceedings of the 23rd Annual ACM Symposium
on Parallelism in Algorithms and Architectures, pp. 215-224, 2011.
- Guy Even and Shakhar Smorodinsky, Hitting Sets Online and
Vertex Ranking, 19th Annual European Symposium (ESA), Lecture
Notes in Computer Science, Vol. 6942, pp. 347-357, Springer, 2011.
- Guy Even, Yaniv Fais, Moti Medina, Shimon Shahar, and Alexander
Zadorojniy, Real-Time Video Streaming in Multi-hop Wireless Static
Ad Hoc Networks, ALGO-SENSORS-2011.
- Guy Even, Yakov Matsri, and Moti Medina, Multi-Hop Routing and
Scheduling in Wireless Networks in the SINR model, ALGOSENSORS-2011.
- Guy Even, Moti Medina, Stefan Schmid, and Gregor Schaffrath,
Competitive and Deterministic Embeddings of Virtual Networks,
best paper in distributed computing track,
L. Bononi et al. (Eds.): ICDCN 2012, LNCS 7129, pp. 106-121. Springer, 2012.
- Nissim Halabi and Guy Even, "Hierarchies of Local-Optimality
Characterizations in Decoding Tanner Codes,"
IEEE International Symposium on Information Theory (ISIT), 2012.
- Nissim Halabi and Guy Even, "Linear-Programming Decoding of Tanner Codes with
Local-Optimality Certificates", IEEE International Symposium on
Information Theory (ISIT), 2012.
- Nissim Halabi and Guy Even, "Local-Optimality Guaranties for
Optimal Decoding Based on Paths", 7th International Symposium on
Turbo Codes & Iterative Information Processing (ISTC), Gothenburg, Sweden, 2012.
- Guy Even, Moti Medina, ``Online Multi-Commodity Flow with High
Demands'', 10th Workshop on Approximation and Online Algorithms
(WAOA), Ljubljana,
Slovenia, 2012.
- Guy Even, ``Real-Time Iterative Systolic Integer Multiplier,''
Israeli Patent Application 103178, Sept. 1992.
- Peter-Michael Seidel and Guy Even, ``Fast IEEE floating-point
adder'', United States Patent Application 20030055859, March 20,
2003.
- Guy Even and Peter-Michael Seidel, ``Pipelined multiplicative
division with IEEE rounding'' United States Patent Application
20040128338, July 1, 2004.
2013-04-28