GUY EVEN
List of Publications

Theses

  1. ``Construction of Small Probabilistic Spaces for Deterministic Simulation,'' supervisor Prof. Oded Goldreich, 1991 (master's thesis).
  2. ``Design of VLSI Circuits Using Retiming,'' supervisors Prof. Benny Chor and Dr. Ami Litman, 1994 (doctoral dissertation).

Books

Textbook

  1. Guy Even and Moti Medina, Logic Design: A Rigorous Approach, Cambridge Univ. Press, Oct. 2012.

Edited Books

  1. Shimon Even, Graph Algorithms, 2nd edition, Cambridge Univ. Press, 2011.
  2. 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.
  3. 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.

Journals

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

  2. Ran Canetti, Guy Even and Oded Goldreich, ``Lower bounds on sampling algorithms for estimating the average '', Information Processing Letters, 53:17-25, 1995.

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

  4. Guy Even,``The Retiming Lemma : A Simple Proof and Applications ,'' Integration, The VLSI Journal, Vol. 20, No. 2, pp. 123-137, March 1996.

  5. Guy Even, ``Real-Time Iterative Systolic Integer Multiplier,'' Integration, The VLSI Journal, Vol. 22, No. 1-2, pp. 23-38, 1997.

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

  7. Guy Even and Ami Litman, ``Overcoming Chip-to-Chip Delays and Clock Skews,'' Integration, The VLSI Journal, Vol. 24, pp. 119-133, 1997.

  8. Guy Even, Seffi Naor, Baruch Schieber, and Madhu Sudan, ``Approximating Minimum Feedback Sets and Multi-Cuts in Directed Graphs,'' Algorithmica, 20 : 151-174, 1998.

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

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

  11. Guy Even and Shimon Even, ``Embedding Interconnection Networks in Grids via the Layered Cross Product'', Networks, Volume 36, Issue 2, pp. 91-95, 2000.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  34. Alexander Zadorojniy, Guy Even, and Adam Shwartz, ``A strongly polynomial algorithm for controlled queues'', Mathematics of Operations Research, articles in advance (Oct. 7, 2009).

  35. Guy Even, Tamir Levi, and Ami Litman, ``Optimal conclusive sets for comparator networks'', Theor. Comput. Sci., 410(14): 1369-1376, 2009.

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

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

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

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

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

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

  42. Guy Even, Moti Medina, Stefan Schmid, and Gregor Schaffrath, Competitive and Deterministic Embeddings of Virtual Networks, accepted to 2012 ICDCN special issue in TCS.

  43. Dmitriy Laschov, Michael Margaliot, and Guy Even, "Observability of Boolean Networks: A Graph-Theoretic Approach", accepted to Automatica, April 2013.

Papers accepted to journals subject to revisions

  1. Guy Even and Nissim Halabi, ``Local-Optimality Guarantees for Optimal Decoding Based on Paths'', accepted to SIAM Journal on Discrete Math, 2013.
  2. Nissim Halabi and Guy Even, "On Decoding Irregular Tanner Codes with Local-Optimality Guaranties", accepted to IEEE trans. on Information Theory, 2013.

Papers submitted to journals

  1. Guy Even and Shakhar Smorodinsky, "Hitting Sets Online and Unique-Max Coloring" submitted to SIAM Journal on Computing, 12-7-2012.

Recent Technical Reports

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

  2. Guy Even, Yakov Matsri, Moti Medina: Multi-Hop Routing and Scheduling in Wireless Networks in the SINR model, CoRR abs/1104.1330, 2011.

  3. Guy Even and Nissim Halabi, ``Message-Passing Algorithms for Packing and Covering Linear Programs with Zero-One Matrices'', arXiv preprint arXiv:1302.3518, 2013.

Chapters in Books

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

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

Conferences

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

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

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

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

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

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

  7. Guy Even, Seffi Naor, Baruch Schieber and Satish Rao, ``Fast Approximate Graph Partitioning Algorithms,'' Eighth Annual ACM-SIAM Symp. on Discrete Algorithms, Jan. 1997.

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

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

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

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

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

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

  14. Guy Even, Sudipto Guha, and Baruch Schieber, ``Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas," STOC 2000, pp. 296-305.

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

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

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

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

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

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

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

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

  23. Guy Even and Peter-M. Seidel, Pipelined Multiplicative Division with IEEE Rounding, in proceedings of ICCD-03, pp. 240-245, Oct. 2003.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  38. Guy Even, Yakov Matsri, and Moti Medina, Multi-Hop Routing and Scheduling in Wireless Networks in the SINR model, ALGOSENSORS-2011.

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

  40. Nissim Halabi and Guy Even, "Hierarchies of Local-Optimality Characterizations in Decoding Tanner Codes," IEEE International Symposium on Information Theory (ISIT), 2012.

  41. Nissim Halabi and Guy Even, "Linear-Programming Decoding of Tanner Codes with Local-Optimality Certificates", IEEE International Symposium on Information Theory (ISIT), 2012.

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

  43. Guy Even, Moti Medina, ``Online Multi-Commodity Flow with High Demands'', 10th Workshop on Approximation and Online Algorithms (WAOA), Ljubljana, Slovenia, 2012.

Patent Applications

  1. Guy Even, ``Real-Time Iterative Systolic Integer Multiplier,'' Israeli Patent Application 103178, Sept. 1992.

  2. Peter-Michael Seidel and Guy Even, ``Fast IEEE floating-point adder'', United States Patent Application 20030055859, March 20, 2003.

  3. Guy Even and Peter-Michael Seidel, ``Pipelined multiplicative division with IEEE rounding'' United States Patent Application 20040128338, July 1, 2004.

About this document ...



2013-04-28