Papers of Michael Langberg
(please read the copyright
notice):
- U. Feige
and M. Langberg.
Approximation
Algorithms for Maximization Problems arising in Graph Partitioning.
Journal of Algorithms 41 (2001), 174-211.
- U. Feige,
M. Karpinski, and M. Langberg.
Improved approximation of Max-Cut on graphs of bounded degree.
Journal of Algorithms 43-2 (2002), 201-219.
Extended
version (ECCC TR00-021), Journal
version.
- U. Feige,
M. Karpinski, and M. Langberg.
A
Note on
Approximating MAX-BISECTION on Regular Graphs.
Information Processing Letters 79 (2001), 181-188.
- U. Feige,
M. Langberg, and K. Nissim.
On
the
hardness of approximating NP witnesses.
Proceedings of APPROX 2000, 120-131 (Springer-Verlag).
- U. Feige
and M. Langberg.
The RPR2
rounding technique for semidefinite programs.
Journal of Algorithms 60-1 (2006), 1-23. Also appeared in proceedings
of ICALP 2001.
- U. Feige,
M. Langberg and G. Schechtman.
Graphs
with tiny vector chromatic numbers and huge chromatic numbers.
SIAM
Journal on Computing 33(6), 1338--1368, 2004. Also appeared in proceedings
of FOCS 2002.
PowerPoint
presentation.
- M. Langberg,
A. Pnueli, and Y. Rodeh.
The
ROBDD
size of simple CNF formulas.
Proceedings of CHARME 2003, 363-377.
- M. Langberg,
A. Sprintson and J. Bruck.
Optimal
Universal Schedules for Discrete Broadcast.
IEEE Transactions on Information Theory 54(9): 4365-4372 (2008).
Also appeared in Proceedings of ISIT 2004, p. 111.
- A. Avidor
and M. Langberg.
The
Multi-Multiway Cut Problem.
Theoretical Computer Science 377(1-3), 35-42, 2007. Also appeared in Proceedings of SWAT 2004,
273-284 (Springer-Verlag).
PowerPoint
presentation.
- M. Langberg.
Testing
the independence number of hypergraphs.
Proceedings of RANDOM 2004, 405-416 (Springer-Verlag).
Also appeared in ECCC
- TR03-076.
PowerPoint
presentation.
- M. Langberg.
Private
codes or Succinct random codes that are (almost) perfect.
Proceedings of FOCS 2004, 325-334.
PowerPoint
presentation.
- M. Langberg,
A. Sprintson and J. Bruck.
Staleness vs. Waiting Time in Universal Discrete Broadcast.
Proceedings of ISIT 2005, 2124-2128.
A previous version under the name: Optimal Schedules
for Asynchronous Transmission of Discrete Packets.
PowerPoint
presentation.
- M. Langberg,
A. Sprintson and J. Bruck.
The encoding
complexity of network coding.
IEEE Transactions on Information Theory 52(6), 2386-2397, 2006 (a
joint special issue with IEEE/ACM Transactions on Networking on Networking
and Information Theory). Also appeared in proceedings of ISIT 2005, 1987-1991.
PowerPoint
presentation.
- S. Jaggi,
M. Langberg, T. Ho, M. Effros.
Correction
of
Adversarial Errors in Networks.
Proceedings of ISIT 2005, 1455-1459.
PowerPoint
presentation.
- J. Gao,
M. Langberg and L. Schulman
Analysis of Incomplete Data and an Intrinsic-Dimension Helly Theorem.
In Discrete & Computational Geometry 40(4): 537-560 (2008).
Also in Proceedings of SODA 2006, 464-473.
- M. Langberg,
A. Sprintson and J. Bruck.
Network Coding: A Computational Perspective.
IEEE Transactions on Information Theory 55(1): 147-157 (2009).
Also in CISS 2006 (invited talk).
- M. Langberg.
Oblivious
channels and their capacity.
IEEE Transactions on Information Theory, 54(1), 424-429, 2008. Also
appeared in proceedings of ISIT 2006,
2739-2743 under the name ‘Oblivious channels’.
- M. Langberg,
Y. Rabani and C. Swamy.
Approximation
Algorithms for Graph Homomorphism Problems.
Proceedings of APPROX 2006, 176-187.
- S. Jaggi, M. Langberg, S. Katti, T. Ho, D. Katabi, M. Medard and M. Effros.
Resilient Network Coding in the Presence of Byzantine Adversaries.
IEEE Transactions on Information Theory (special issue on information-theoretic security) 54(6), 2596-2603, 2008.
Also appeared in INFOCOM, 616-624, 2007 and in 3rd Workshop on Network Coding, Theory,
and Applications (NetCod) 2007 (invited talk).
- J. Bruck, M. Langberg and M. Schwartz.
Distributed Broadcasting and Mapping Protocols in Directed Anonymous Networks.
PODC 2007, 382-383 (2 page brief announcement).
- M. Langberg and L. Schulman.
Contraction and expansion of convex sets.
Discrete & Computational Geometry 42(4): 594-614 (2009), Also appeared in CCCG 2007, 25-28.
- S. Jaggi and M. Langberg.
Resilient network codes in the presence of eavesdropping Byzantine
adversaries
Proceedings of ISIT 2007, 541-545.
- L. Nutman and M. Langberg.
Adversarial Models and Resilient
Schemes for Network Coding.
In proceedings of IEEE International Symposium on Information Theory (ISIT) 2008, 171-175.
- M. Langberg and A. Sprintson.
On the Hardness of Approximating the Network Coding Capacity
(an errata).
In proceedings of IEEE International Symposium on Information Theory (ISIT) 2008, 315-319.
- S. Shenvi, S. Jaggi, B. K. Dey and M. Langberg.
``Real'' Slepian-Wolf coding using Random (1,-1) Matrices.
In proceedings of IEEE International Symposium on Information Theory (ISIT) 2008.
- G. Kortsarz, Z. Nutov and M. Langberg.
Approximating Maximum Subgraphs Without Short Cycles.
In proceedings of 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2008, 118-131.
- S. Chechik, M. Langberg, D. Peleg and L. Roditty.
Fault-Tolerant Spanners for General Graphs.
In proceedings of 41st ACM Symposium on Theory of Computing (STOC), 2009, 435-444.
- M. Langberg, S. Jaggi and B. K. Dey.
Binary Causal-Adversary Channels.
In proceedings of IEEE International Symposium on Information Theory (ISIT) 2009.
- M. Langberg and A. Ramamoorthy.
Communicating the sum of sources in a 3-sources/3-terminals network.
In proceedings of IEEE International Symposium on Information Theory (ISIT) 2009.
- A. Jiang, M. Langberg, M. Schwartz and J. Bruck.
Universal Rewriting in Constrained Memories.
In proceedings of IEEE International Symposium on Information Theory (ISIT) 2009.
- B. K. Dey, S. Jaggi and M. Langberg.
Codes against Online Adversaries.
In proceedings of the Forty-Seventh Annual Allerton Conference on Communication, Control, and Computing, 2009.
- M. Langberg and M. Medard.
On the Multiple Unicast Network Coding Conjecture.
In proceedings of the Forty-Seventh Annual Allerton Conference on Communication, Control, and Computing, 2009.
- A. Jiang, M. Langberg, R. Mateescu and J. Bruck.
Data Movement in Flash Memories.
In proceedings of the Forty-Seventh Annual Allerton Conference on Communication, Control, and Computing, 2009.
- M. Langberg and L. J. Schulman.
Universal epsilon-approximators for integrals.
In proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010, 598-607.
- H. Yao, D. Silva, S. Jaggi, M. Langberg.
Network Codes Resilient to Jamming and Eavesdropping.
To appear in IEEE International Symposium on Network Coding (NetCod) 2010.
- R. Bar-Yanai, M. Langberg, D. Peleg and L. Roditty.
Realtime Classification for Encrypted traffic.
To appear in proceedings of 9th International Symposium on Experimental Algorithms (SEA) 2010.
- A. Jiang, M. Langberg, R. Mateescu and J. Bruck.
Information Allocation and Aggregation in Flash Memories.
To appear in proceedings of IEEE International Symposium on Information Theory (ISIT) 2010.
- B. K. Dey, S. Jaggi, M. Langberg, and A. Sarwate.
Codes against Delayed Adversaries.
To appear in proceedings of IEEE International Symposium on Information Theory (ISIT) 2010.
- R. A. Costa, M. Langberg, and J. Barros.
One-Shot Capacity of Discrete Channels.
To appear in proceedings of IEEE International Symposium on Information Theory (ISIT) 2010.
- A. Ramamoorthy and M. Langberg.
Communicating the sum of sources in a 3-sources/3-terminals network; revisited.
To appear in proceedings of IEEE International Symposium on Information Theory (ISIT) 2010.
- J. Gao, M. Langberg and L. Schulman.
Clustering lines: classification of incomplete data.
To appear in Transactions on Algorithms, 2010.
- S. Chechik, M. Langberg, D. Peleg and L. Roditty.
f-Sensitivity Distance Oracles and Routing Schemes.
To appear in proceedings of 18th annual European Symposium on Algorithms (ESA), 2010.
Theses